Submission #1635003
Source Code Expand
#include <algorithm> #include <utility> #include <vector> using Graph = std::vector<std::vector<int>>; using Edge = std::pair<int, int>; class BridgeHelper { const Graph& graph; std::vector<int> ord, low; int k = 0; public: std::vector<Edge> bridges; BridgeHelper(const Graph& graph) : graph(graph), ord(graph.size(), -1), low(graph.size()) { for (int u = 0; u < graph.size(); ++u) { if (ord[u] >= 0) continue; dfs(u); } } bool is_bridge(int u, int v) const { if (ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: void dfs(int u, int p = -1) { ord[u] = low[u] = k; ++k; for (int v : graph[u]) { if (v == p) continue; if (ord[v] >= 0) { low[u] = std::min(low[u], ord[v]); } else { dfs(v, u); low[u] = std::min(low[u], low[v]); } if (is_bridge(u, v)) bridges.emplace_back(u, v); } } }; struct BECC { std::vector<std::vector<int>> comps; std::vector<int> belongs; const BridgeHelper bridge_helper; private: const Graph& graph; public: BECC(const Graph& graph) : graph(graph), bridge_helper(graph), belongs(graph.size(), -1) { for (const auto& bridge : bridge_helper.bridges) { add_component(bridge.first); add_component(bridge.second); } add_component(0); } Graph to_tree() const { Graph tree(comps.size()); for (const auto& bridge : bridge_helper.bridges) { int u = belongs[bridge.first], v = belongs[bridge.second]; tree[u].emplace_back(v); tree[v].emplace_back(u); } return tree; } private: void fill_component(int c, int u) { comps[c].emplace_back(u); belongs[u] = c; for (int v : graph[u]) { if (belongs[v] >= 0) continue; if (bridge_helper.is_bridge(u, v)) continue; fill_component(c, v); } } void add_component(int u) { if (belongs[u] >= 0) return; comps.emplace_back(); fill_component(comps.size() - 1, u); } }; struct LCA { private: const Graph& tree; const int root; std::vector<int> depth; std::vector<std::vector<int>> parent; public: LCA(const Graph& tree, int root) : tree(tree), root(root), depth(tree.size()), parent(std::__lg(tree.size()) + 1, std::vector<int>(tree.size())) { build(root); for (int k = 0; k + 1 < parent.size(); ++k) { for (int u = 0; u < tree.size(); ++u) { if (parent[k][u] < 0) { parent[k + 1][u] = -1; } else { parent[k + 1][u] = parent[k][parent[k][u]]; } } } } int query(int u, int v) const { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < parent.size(); ++k) { if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; } if (u == v) return u; for (int k = parent.size() - 1; k >= 0; --k) { if (parent[k][u] == parent[k][v]) continue; u = parent[k][u]; v = parent[k][v]; } return parent[0][u]; } int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[query(u, v)]; } private: void build(int u, int p = -1, int d = 0) { parent[0][u] = p; depth[u] = d; for (int v : tree[u]) { if (v == p) continue; build(v, u, d + 1); } } }; #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); ++i) inline int in() { int x; scanf("%d", &x); return x; } int main() { int N = in(), M = in(); Graph G(N); rep(i, M) { int u = in() - 1, v = in() - 1; G[u].emplace_back(v); G[v].emplace_back(u); } BECC becc(G); Graph tree = becc.to_tree(); LCA lca(tree, 0); int Q = in(); rep(i, Q) { int A = in() - 1, B = in() - 1, C = in() - 1; int X = becc.belongs[A], Y = becc.belongs[B], Z = becc.belongs[C]; if (lca.dist(X, Z) == lca.dist(X, Y) + lca.dist(Y, Z)) { puts("OK"); } else { puts("NG"); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 旅行会社高橋君 |
User | orisano |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 4092 Byte |
Status | AC |
Exec Time | 201 ms |
Memory | 29932 KB |
Compile Error
./Main.cpp: In function ‘int in()’: ./Main.cpp:143:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &x); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_0.txt, sample_1.txt, sample_2.txt |
All | bigcycleandsub_0.txt, bigcycleandsub_1.txt, cluster_0.txt, cluster_1.txt, cluster_2.txt, cluster_3.txt, cluster_4.txt, cycleline_0.txt, cycleline_1.txt, cycleline_2.txt, cycleline_3.txt, cycleline_4.txt, cycletree_0.txt, cycletree_1.txt, cycletree_2.txt, cycletree_3.txt, cycletree_4.txt, large_0.txt, large_1.txt, large_2.txt, line_0.txt, line_1.txt, lineandsub_0.txt, lineandsub_1.txt, lineandsub_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_2.txt, maxrandandsub_0.txt, maxrandandsub_1.txt, maxrandandsub_2.txt, maxrandandsub_3.txt, maxrandandsub_4.txt, med_0.txt, med_1.txt, med_2.txt, med_3.txt, med_4.txt, med_5.txt, med_6.txt, med_7.txt, med_8.txt, med_9.txt, perfect_0.txt, perfect_1.txt, perfect_2.txt, sample_0.txt, sample_1.txt, sample_2.txt, small_0.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt, star_0.txt, star_1.txt, star_2.txt, tencluster_0.txt, tencluster_1.txt, tencluster_2.txt, tencluster_3.txt, tencluster_4.txt, tree_0.txt, tree_1.txt, tree_2.txt, verysmall_0.txt, verysmall_1.txt, verysmall_2.txt, verysmall_3.txt, verysmall_4.txt, verysmall_5.txt, verysmall_6.txt, verysmall_7.txt, verysmall_8.txt, verysmall_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
bigcycleandsub_0.txt | AC | 84 ms | 12792 KB |
bigcycleandsub_1.txt | AC | 84 ms | 12792 KB |
cluster_0.txt | AC | 115 ms | 9088 KB |
cluster_1.txt | AC | 117 ms | 9088 KB |
cluster_2.txt | AC | 115 ms | 8960 KB |
cluster_3.txt | AC | 115 ms | 9216 KB |
cluster_4.txt | AC | 115 ms | 9088 KB |
cycleline_0.txt | AC | 112 ms | 8960 KB |
cycleline_1.txt | AC | 117 ms | 9088 KB |
cycleline_2.txt | AC | 115 ms | 8960 KB |
cycleline_3.txt | AC | 116 ms | 8960 KB |
cycleline_4.txt | AC | 115 ms | 8960 KB |
cycletree_0.txt | AC | 106 ms | 8832 KB |
cycletree_1.txt | AC | 103 ms | 8832 KB |
cycletree_2.txt | AC | 106 ms | 8832 KB |
cycletree_3.txt | AC | 106 ms | 8832 KB |
cycletree_4.txt | AC | 107 ms | 8832 KB |
large_0.txt | AC | 104 ms | 10368 KB |
large_1.txt | AC | 19 ms | 1792 KB |
large_2.txt | AC | 75 ms | 9856 KB |
line_0.txt | AC | 142 ms | 29804 KB |
line_1.txt | AC | 84 ms | 29036 KB |
lineandsub_0.txt | AC | 194 ms | 29036 KB |
lineandsub_1.txt | AC | 195 ms | 29932 KB |
lineandsub_2.txt | AC | 194 ms | 29164 KB |
maxrand_0.txt | AC | 112 ms | 12536 KB |
maxrand_1.txt | AC | 111 ms | 12536 KB |
maxrand_2.txt | AC | 120 ms | 12668 KB |
maxrandandsub_0.txt | AC | 129 ms | 13432 KB |
maxrandandsub_1.txt | AC | 126 ms | 13432 KB |
maxrandandsub_2.txt | AC | 134 ms | 13432 KB |
maxrandandsub_3.txt | AC | 126 ms | 13432 KB |
maxrandandsub_4.txt | AC | 120 ms | 13432 KB |
med_0.txt | AC | 2 ms | 256 KB |
med_1.txt | AC | 1 ms | 256 KB |
med_2.txt | AC | 1 ms | 256 KB |
med_3.txt | AC | 2 ms | 256 KB |
med_4.txt | AC | 2 ms | 384 KB |
med_5.txt | AC | 2 ms | 256 KB |
med_6.txt | AC | 2 ms | 384 KB |
med_7.txt | AC | 2 ms | 384 KB |
med_8.txt | AC | 1 ms | 256 KB |
med_9.txt | AC | 2 ms | 256 KB |
perfect_0.txt | AC | 30 ms | 1280 KB |
perfect_1.txt | AC | 21 ms | 1152 KB |
perfect_2.txt | AC | 30 ms | 1280 KB |
sample_0.txt | AC | 1 ms | 256 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
small_0.txt | AC | 1 ms | 256 KB |
small_1.txt | AC | 1 ms | 256 KB |
small_2.txt | AC | 1 ms | 256 KB |
small_3.txt | AC | 1 ms | 256 KB |
small_4.txt | AC | 1 ms | 256 KB |
small_5.txt | AC | 1 ms | 256 KB |
small_6.txt | AC | 1 ms | 256 KB |
small_7.txt | AC | 1 ms | 256 KB |
small_8.txt | AC | 1 ms | 256 KB |
small_9.txt | AC | 1 ms | 256 KB |
star_0.txt | AC | 155 ms | 27116 KB |
star_1.txt | AC | 157 ms | 27116 KB |
star_2.txt | AC | 157 ms | 27116 KB |
tencluster_0.txt | AC | 114 ms | 9600 KB |
tencluster_1.txt | AC | 114 ms | 9472 KB |
tencluster_2.txt | AC | 114 ms | 9344 KB |
tencluster_3.txt | AC | 115 ms | 9728 KB |
tencluster_4.txt | AC | 109 ms | 9600 KB |
tree_0.txt | AC | 201 ms | 26480 KB |
tree_1.txt | AC | 201 ms | 27248 KB |
tree_2.txt | AC | 196 ms | 26608 KB |
verysmall_0.txt | AC | 1 ms | 256 KB |
verysmall_1.txt | AC | 1 ms | 256 KB |
verysmall_2.txt | AC | 1 ms | 256 KB |
verysmall_3.txt | AC | 1 ms | 256 KB |
verysmall_4.txt | AC | 1 ms | 256 KB |
verysmall_5.txt | AC | 1 ms | 256 KB |
verysmall_6.txt | AC | 1 ms | 256 KB |
verysmall_7.txt | AC | 1 ms | 256 KB |
verysmall_8.txt | AC | 1 ms | 256 KB |
verysmall_9.txt | AC | 1 ms | 256 KB |