Submission #818954
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 BICC { std::vector<std::vector<int>> comps; std::vector<int> belongs; const BridgeHelper bridge_helper; private: const Graph& graph; public: BICC(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); } }; constexpr int roundup_log2(int x, int a = 1, int k = 0) { return a < x ? roundup_log2(x, a + a, k + 1) : std::max(k, 1); } 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(roundup_log2(tree.size()), 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); } BICC bicc(G); Graph tree = bicc.to_tree(); LCA lca(tree, 0); int Q = in(); rep(i, Q) { int A = in() - 1, B = in() - 1, C = in() - 1; int X = bicc.belongs[A], Y = bicc.belongs[B], Z = bicc.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++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 4221 Byte |
Status | AC |
Exec Time | 398 ms |
Memory | 30576 KB |
Compile Error
./Main.cpp: In function ‘int in()’: ./Main.cpp:147: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, 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 | 359 ms | 13428 KB |
bigcycleandsub_1.txt | AC | 319 ms | 13436 KB |
cluster_0.txt | AC | 243 ms | 9732 KB |
cluster_1.txt | AC | 242 ms | 9860 KB |
cluster_2.txt | AC | 239 ms | 9732 KB |
cluster_3.txt | AC | 240 ms | 9864 KB |
cluster_4.txt | AC | 238 ms | 9776 KB |
cycleline_0.txt | AC | 235 ms | 9616 KB |
cycleline_1.txt | AC | 237 ms | 9640 KB |
cycleline_2.txt | AC | 236 ms | 9676 KB |
cycleline_3.txt | AC | 238 ms | 9668 KB |
cycleline_4.txt | AC | 235 ms | 9672 KB |
cycletree_0.txt | AC | 222 ms | 9412 KB |
cycletree_1.txt | AC | 237 ms | 9480 KB |
cycletree_2.txt | AC | 226 ms | 9512 KB |
cycletree_3.txt | AC | 225 ms | 9476 KB |
cycletree_4.txt | AC | 222 ms | 9488 KB |
large_0.txt | AC | 221 ms | 11312 KB |
large_1.txt | AC | 64 ms | 2684 KB |
large_2.txt | AC | 164 ms | 10760 KB |
line_0.txt | AC | 309 ms | 30576 KB |
line_1.txt | AC | 218 ms | 29872 KB |
lineandsub_0.txt | AC | 381 ms | 29560 KB |
lineandsub_1.txt | AC | 398 ms | 30188 KB |
lineandsub_2.txt | AC | 383 ms | 29812 KB |
maxrand_0.txt | AC | 240 ms | 13440 KB |
maxrand_1.txt | AC | 239 ms | 13356 KB |
maxrand_2.txt | AC | 240 ms | 13320 KB |
maxrandandsub_0.txt | AC | 261 ms | 14080 KB |
maxrandandsub_1.txt | AC | 260 ms | 14140 KB |
maxrandandsub_2.txt | AC | 257 ms | 14080 KB |
maxrandandsub_3.txt | AC | 254 ms | 14080 KB |
maxrandandsub_4.txt | AC | 265 ms | 14124 KB |
med_0.txt | AC | 34 ms | 1216 KB |
med_1.txt | AC | 30 ms | 1128 KB |
med_2.txt | AC | 30 ms | 1224 KB |
med_3.txt | AC | 31 ms | 1212 KB |
med_4.txt | AC | 36 ms | 1328 KB |
med_5.txt | AC | 31 ms | 1260 KB |
med_6.txt | AC | 31 ms | 1324 KB |
med_7.txt | AC | 33 ms | 1308 KB |
med_8.txt | AC | 32 ms | 1216 KB |
med_9.txt | AC | 31 ms | 1192 KB |
perfect_0.txt | AC | 86 ms | 2096 KB |
perfect_1.txt | AC | 68 ms | 2188 KB |
perfect_2.txt | AC | 85 ms | 2096 KB |
sample_0.txt | AC | 29 ms | 1220 KB |
sample_1.txt | AC | 32 ms | 1284 KB |
sample_2.txt | AC | 32 ms | 1288 KB |
small_0.txt | AC | 33 ms | 1284 KB |
small_1.txt | AC | 31 ms | 1156 KB |
small_2.txt | AC | 30 ms | 1276 KB |
small_3.txt | AC | 30 ms | 1280 KB |
small_4.txt | AC | 32 ms | 1340 KB |
small_5.txt | AC | 30 ms | 1284 KB |
small_6.txt | AC | 32 ms | 1284 KB |
small_7.txt | AC | 31 ms | 1348 KB |
small_8.txt | AC | 30 ms | 1340 KB |
small_9.txt | AC | 32 ms | 1220 KB |
star_0.txt | AC | 314 ms | 27760 KB |
star_1.txt | AC | 311 ms | 27760 KB |
star_2.txt | AC | 314 ms | 27736 KB |
tencluster_0.txt | AC | 239 ms | 10304 KB |
tencluster_1.txt | AC | 241 ms | 10152 KB |
tencluster_2.txt | AC | 235 ms | 10032 KB |
tencluster_3.txt | AC | 240 ms | 10376 KB |
tencluster_4.txt | AC | 242 ms | 10276 KB |
tree_0.txt | AC | 372 ms | 27188 KB |
tree_1.txt | AC | 374 ms | 27168 KB |
tree_2.txt | AC | 371 ms | 27188 KB |
verysmall_0.txt | AC | 32 ms | 1220 KB |
verysmall_1.txt | AC | 31 ms | 1180 KB |
verysmall_2.txt | AC | 32 ms | 1260 KB |
verysmall_3.txt | AC | 32 ms | 1204 KB |
verysmall_4.txt | AC | 31 ms | 1200 KB |
verysmall_5.txt | AC | 32 ms | 1204 KB |
verysmall_6.txt | AC | 31 ms | 1184 KB |
verysmall_7.txt | AC | 29 ms | 1220 KB |
verysmall_8.txt | AC | 31 ms | 1220 KB |
verysmall_9.txt | AC | 33 ms | 1292 KB |