Submission #4065801
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new UndirectedGraph(N); foreach (i; 0..M) { s = readln.split.map!(to!int); G.add_edge(s[0]-1, s[1]-1); } auto T = new BridgeBlockTree(G); auto L = new LCA(T.block.length.to!int, 0); foreach (i; 0..T.block.length.to!int) { foreach (j; T.adj[i]) { if (i < j) { L.add_edge(i, j); } } } bool check() { s = readln.split.map!(to!int); auto a = T.index[s[0] - 1]; auto b = T.index[s[1] - 1]; auto c = T.index[s[2] - 1]; auto ab = L.lca(a, b); auto bc = L.lca(b, c); auto ca = L.lca(c, a); if (ca == a) { return ab == a && bc == b; } else if (ca == c) { return bc == c && ab == b; } else { return ab == ca || bc == ca; } } auto Q = readln.chomp.to!int; while (Q--) { writeln( check ? "OK" : "NG" ); } } class UndirectedGraph { int N; int[][] adj; this (int N) { this.N = N; adj = new int[][](N); } void add_edge(int u, int v) { adj[u] ~= v; adj[v] ~= u; } } class BridgeBlockTree : UndirectedGraph { // 二重辺連結成分分解 (橋で分解したあとの木) int[] index; int[][] block; Tuple!(int, int)[] bridges; this (UndirectedGraph g) { int n = 0; int cnt = 0; bridges = detect_bridges(g); auto is_bridge = new bool[int][](g.N); foreach (b; bridges) { is_bridge[b[0]][b[1]] = true; is_bridge[b[1]][b[0]] = true; } index = new int[](g.N); auto used = new bool[](g.N); void dfs(int n) { index[n] = block.length.to!int - 1; block.back ~= n; used[n] = true; foreach (m; g.adj[n]) { if (used[m] || m in is_bridge[n]) continue; dfs(m); } } foreach (u; 0..g.N) { if (used[u]) continue; block.length += 1; dfs(u); } super(block.length.to!int); foreach (u; 0..g.N) { foreach (v; g.adj[u]) { if (u < v && index[u] != index[v]) { adj[index[u]] ~= index[v]; adj[index[v]] ~= index[u]; } } } } Tuple!(int, int)[] detect_bridges(UndirectedGraph g) { Tuple!(int, int)[] bridges; int cnt = 0; auto ord = new int[](g.N); auto low = new int[](g.N); fill(ord, -1); fill(low, -1); void dfs(int n, int p) { ord[n] = low[n] = cnt++; foreach (m; g.adj[n]) { if (m == p) continue; if (ord[m] == -1) dfs(m, n); low[n] = min(low[n], low[m]); if (ord[n] < low[m]) bridges ~= tuple(n, m); } } dfs(0, -1); return bridges; } } class LCA { int n, root, lgn; int[][] g; int[] depth; int[][] dp; bool constructed = false; this(int n, int root) { this.n = n; this.root = root; lgn = bsr(n) + 1; g = new int[][](n); depth = new int[](n); dp = new int[][](n, lgn); } void add_edge(int u, int v) { g[u] ~= v; g[v] ~= u; } void construct() { auto stack = new Tuple!(int, int, int)[](n+10); int sp = 0; stack[0] = tuple(root, -1, 0); while (sp >= 0) { auto u = stack[sp][0]; auto p = stack[sp][1]; auto d = stack[sp][2]; sp -= 1; dp[u][0] = p; depth[u] = d; foreach (v; g[u]) if (v != p) stack[++sp] = tuple(v, u, d+1); } foreach (k; 0..lgn-1) foreach (i; 0..n) dp[i][k+1] = (dp[i][k] == -1) ? -1 : dp[dp[i][k]][k]; constructed = true; } void dfs(int u, int p, int d) { dp[u][0] = p; depth[u] = d; foreach (v; g[u]) if (v != p) dfs(v, u, d+1); } int lca(int a, int b) { if (!constructed) construct; if (depth[a] < depth[b]) swap(a, b); int diff = depth[a] - depth[b]; foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[a][i]; if (a == b) return a; int K = lgn; while (dp[a][0] != dp[b][0]) { foreach_reverse (k; 0..lgn) { if (dp[a][k] != dp[b][k]) { a = dp[a][k]; b = dp[b][k]; K = k; } } } return dp[a][0]; } }
Submission Info
Submission Time | |
---|---|
Task | D - 旅行会社高橋君 |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 5207 Byte |
Status | WA |
Exec Time | 450 ms |
Memory | 77948 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 197 ms | 34300 KB |
bigcycleandsub_1.txt | WA | 208 ms | 34940 KB |
cluster_0.txt | WA | 270 ms | 24188 KB |
cluster_1.txt | WA | 268 ms | 24188 KB |
cluster_2.txt | WA | 265 ms | 24060 KB |
cluster_3.txt | WA | 267 ms | 24188 KB |
cluster_4.txt | AC | 265 ms | 24060 KB |
cycleline_0.txt | WA | 219 ms | 13564 KB |
cycleline_1.txt | WA | 227 ms | 13564 KB |
cycleline_2.txt | WA | 236 ms | 13436 KB |
cycleline_3.txt | WA | 232 ms | 13436 KB |
cycleline_4.txt | WA | 218 ms | 13564 KB |
cycletree_0.txt | WA | 221 ms | 22268 KB |
cycletree_1.txt | WA | 219 ms | 13052 KB |
cycletree_2.txt | WA | 219 ms | 13052 KB |
cycletree_3.txt | WA | 218 ms | 13052 KB |
cycletree_4.txt | WA | 220 ms | 13052 KB |
large_0.txt | AC | 252 ms | 30204 KB |
large_1.txt | AC | 47 ms | 7804 KB |
large_2.txt | AC | 167 ms | 19708 KB |
line_0.txt | WA | 359 ms | 73084 KB |
line_1.txt | WA | 292 ms | 64380 KB |
lineandsub_0.txt | WA | 450 ms | 75388 KB |
lineandsub_1.txt | WA | 421 ms | 77948 KB |
lineandsub_2.txt | WA | 425 ms | 76412 KB |
maxrand_0.txt | AC | 266 ms | 32892 KB |
maxrand_1.txt | AC | 270 ms | 32892 KB |
maxrand_2.txt | AC | 271 ms | 32892 KB |
maxrandandsub_0.txt | WA | 300 ms | 36988 KB |
maxrandandsub_1.txt | WA | 298 ms | 35452 KB |
maxrandandsub_2.txt | WA | 297 ms | 36348 KB |
maxrandandsub_3.txt | WA | 311 ms | 35452 KB |
maxrandandsub_4.txt | WA | 296 ms | 36220 KB |
med_0.txt | AC | 4 ms | 636 KB |
med_1.txt | AC | 2 ms | 380 KB |
med_2.txt | AC | 3 ms | 508 KB |
med_3.txt | AC | 3 ms | 636 KB |
med_4.txt | AC | 4 ms | 764 KB |
med_5.txt | AC | 3 ms | 636 KB |
med_6.txt | AC | 3 ms | 764 KB |
med_7.txt | AC | 3 ms | 636 KB |
med_8.txt | AC | 2 ms | 380 KB |
med_9.txt | AC | 3 ms | 636 KB |
perfect_0.txt | AC | 91 ms | 8828 KB |
perfect_1.txt | AC | 71 ms | 7548 KB |
perfect_2.txt | AC | 94 ms | 8828 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 | WA | 2 ms | 380 KB |
small_1.txt | AC | 2 ms | 380 KB |
small_2.txt | AC | 1 ms | 256 KB |
small_3.txt | WA | 1 ms | 256 KB |
small_4.txt | AC | 2 ms | 380 KB |
small_5.txt | AC | 2 ms | 380 KB |
small_6.txt | AC | 1 ms | 256 KB |
small_7.txt | WA | 2 ms | 380 KB |
small_8.txt | WA | 2 ms | 380 KB |
small_9.txt | AC | 1 ms | 380 KB |
star_0.txt | WA | 338 ms | 73724 KB |
star_1.txt | WA | 326 ms | 74620 KB |
star_2.txt | WA | 347 ms | 73980 KB |
tencluster_0.txt | WA | 261 ms | 25340 KB |
tencluster_1.txt | WA | 261 ms | 24828 KB |
tencluster_2.txt | WA | 268 ms | 24700 KB |
tencluster_3.txt | WA | 264 ms | 25468 KB |
tencluster_4.txt | WA | 265 ms | 25468 KB |
tree_0.txt | WA | 440 ms | 71420 KB |
tree_1.txt | WA | 422 ms | 71420 KB |
tree_2.txt | WA | 430 ms | 72060 KB |
verysmall_0.txt | AC | 1 ms | 256 KB |
verysmall_1.txt | WA | 1 ms | 256 KB |
verysmall_2.txt | WA | 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 | WA | 1 ms | 256 KB |
verysmall_7.txt | AC | 1 ms | 256 KB |
verysmall_8.txt | WA | 1 ms | 256 KB |
verysmall_9.txt | AC | 1 ms | 256 KB |