Submission #3418630
Source Code Expand
import algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future var input : seq[string] = @[] var in_cnt = 0 proc gs() : string = if input.len == in_cnt: in_cnt = 0 input = stdin.readline.split in_cnt += 1 return input[in_cnt - 1] proc gi() : int = return gs().parseInt proc gf() : float = return gs().parseFloat type Edge* = object to : int Graph*[E] = seq[seq[E]] proc newGraph*[E](n : int) : Graph[E] = var g : Graph[E] = newSeqWith(n , newSeq[E](0)) return g proc lowlink*[E](g : Graph[E]) : seq[tuple[a : int , b : int]] = var bridge : seq[tuple[a : int , b : int]] = @[] n = g.len used = newSeqWith(n , false) ord = newSeqWith(n , 0) low = newSeqWith(n , 0) dfs : proc(v , K , f : int) : int dfs = proc(v , K , f : int) : int = var k = K used[v] = true ord[v] = k low[v] = ord[v] inc(k) for e in g[v]: if not used[e.to]: k = dfs(e.to , k , v) low[v] = min(low[v] , low[e.to]) if ord[v] < low[e.to]: bridge.add((min(v , e.to) , max(v , e.to))) elif e.to != f: low[v] = min(low[v] , ord[e.to]) return k discard dfs(0,0,-1) return bridge proc buildTwoEdgeConnectedComponent*[E](g : Graph[E]) : tuple[cmp : seq[int] , tree : Graph[E]] = var bridge = g.lowlink st = toSet(bridge) n = g.len cmp = newSeqWith(n , -1) dfs : proc(v , f , k : int) k = 0 dfs = proc(v,f,k : int) = cmp[v] = k for e in g[v]: if cmp[e.to] == -1 and not st.contains((min(v,e.to) , max(v,e.to))): dfs(e.to , v , k) for i in 0..<n: if cmp[i] == -1: dfs(i , -1 , k) inc(k) var tree = newGraph[Edge](k) for e in bridge: tree[cmp[e.a]].add(Edge(to : cmp[e.b])) tree[cmp[e.b]].add(Edge(to : cmp[e.a])) return (cmp , tree) type LowestCommonAncestor = object n : int log2_n : int parent : seq[seq[int]] depth : seq[int] proc initLowestCommonAncestor*[E](g : Graph[E]) : LowestCommonAncestor = var lca : LowestCommonAncestor lca.n = g.len lca.log2_n = ((int)log2((float)lca.n) + 2) lca.parent = newSeqWith(lca.log2_n , newSeqWith(lca.n,0)) lca.depth = newSeqWith(lca.n , 0) var dfs : proc(v , f , d : int) dfs = proc(v,f,d : int) = lca.parent[0][v] = f lca.depth[v] = d for e in g[v]: if e.to != f: dfs(e.to , v , d + 1) dfs(0,-1,0) for k in 0..<lca.log2_n-1: for v in 0..<lca.n: if lca.parent[k][v] < 0: lca.parent[k + 1][v] = -1 else: lca.parent[k + 1][v] = lca.parent[k][lca.parent[k][v]] return lca proc getLowestCommonAncestor*(lca : LowestCommonAncestor,a : int , b : int) : tuple[parent : int , depth : int]= var u = a v = b if lca.depth[u] > lca.depth[v]: swap(u,v) for k in 0..<lca.log2_n: if (((lca.depth[v] - lca.depth[u]) shr k) and 1) == 1: v = lca.parent[k][v] if u == v: return (u , lca.depth[u]) for k in countdown(lca.log2_n - 1 , 0): if lca.parent[k][u] != lca.parent[k][v]: u = lca.parent[k][u] v = lca.parent[k][v] u = lca.parent[0][u] return (u , lca.depth[u]) proc dist*(lca : LowestCommonAncestor , a : int , b : int) : int = return lca.depth[a] + lca.depth[b] - lca.getLowestCommonAncestor(a , b).depth * 2 var N = gi() var M = gi() var G = newGraph[Edge](N) for i in 1..M: var a = gi() b = gi() dec(a) dec(b) G[a].add(Edge(to : b)) G[b].add(Edge(to : a)) var p = G.buildTwoEdgeConnectedComponent var lca = p.tree.initLowestCommonAncestor var cmp = p.cmp var Q = gi() for i in 1..Q: var a = gi() b = gi() c = gi() a = cmp[a - 1] b = cmp[b - 1] c = cmp[c - 1] if lca.dist(a,b) + lca.dist(b,c) == lca.dist(a , c): echo "OK" else: echo "NG"
Submission Info
Submission Time | |
---|---|
Task | D - 旅行会社高橋君 |
User | niuez |
Language | Nim (0.13.0) |
Score | 100 |
Code Size | 3890 Byte |
Status | AC |
Exec Time | 737 ms |
Memory | 89368 KB |
Compile Error
Hint: system [Processing] Hint: Main [Processing] Hint: algorithm [Processing] Hint: tables [Processing] Hint: hashes [Processing] Hint: strutils [Processing] Hint: parseutils [Processing] Hint: etcpriv [Processing] Hint: math [Processing] Hint: times [Processing] Hint: sets [Processing] Hint: os [Processing] Hint: posix [Processing] Hint: lists [Processing] Hint: queues [Processing] Hint: intsets [Processing] Hint: critbits [Processing] lib/pure/collections/critbits.nim(125, 7) Hint: 'n' is declared but not used [XDeclaredButNotUsed] Hint: sequtils [Processing] Hint: future [Processing] Hint: macros [Processing] Main.nim(15, 6) Hint: 'Main.gf()' is declared but not used [XDeclaredButNotUsed] Hint: [Link] Hint: operation successful (25585 lines compiled; 2.661 sec total; 26.266MB; Release Build) [SuccessX]
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 | 391 ms | 49648 KB |
bigcycleandsub_1.txt | AC | 392 ms | 49648 KB |
cluster_0.txt | AC | 436 ms | 37360 KB |
cluster_1.txt | AC | 442 ms | 37488 KB |
cluster_2.txt | AC | 444 ms | 37104 KB |
cluster_3.txt | AC | 443 ms | 37360 KB |
cluster_4.txt | AC | 435 ms | 37232 KB |
cycleline_0.txt | AC | 437 ms | 36080 KB |
cycleline_1.txt | AC | 447 ms | 35952 KB |
cycleline_2.txt | AC | 457 ms | 35824 KB |
cycleline_3.txt | AC | 453 ms | 35824 KB |
cycleline_4.txt | AC | 437 ms | 36336 KB |
cycletree_0.txt | AC | 448 ms | 35696 KB |
cycletree_1.txt | AC | 443 ms | 35440 KB |
cycletree_2.txt | AC | 445 ms | 35440 KB |
cycletree_3.txt | AC | 450 ms | 35696 KB |
cycletree_4.txt | AC | 446 ms | 35696 KB |
large_0.txt | AC | 376 ms | 39152 KB |
large_1.txt | AC | 80 ms | 6140 KB |
large_2.txt | AC | 272 ms | 36476 KB |
line_0.txt | AC | 526 ms | 89368 KB |
line_1.txt | AC | 327 ms | 86612 KB |
lineandsub_0.txt | AC | 735 ms | 85656 KB |
lineandsub_1.txt | AC | 716 ms | 88808 KB |
lineandsub_2.txt | AC | 737 ms | 87972 KB |
maxrand_0.txt | AC | 436 ms | 46448 KB |
maxrand_1.txt | AC | 450 ms | 46448 KB |
maxrand_2.txt | AC | 443 ms | 46448 KB |
maxrandandsub_0.txt | AC | 486 ms | 50800 KB |
maxrandandsub_1.txt | AC | 470 ms | 50800 KB |
maxrandandsub_2.txt | AC | 477 ms | 50672 KB |
maxrandandsub_3.txt | AC | 465 ms | 50672 KB |
maxrandandsub_4.txt | AC | 467 ms | 50800 KB |
med_0.txt | AC | 4 ms | 636 KB |
med_1.txt | AC | 3 ms | 380 KB |
med_2.txt | AC | 3 ms | 508 KB |
med_3.txt | AC | 3 ms | 636 KB |
med_4.txt | AC | 5 ms | 764 KB |
med_5.txt | AC | 3 ms | 636 KB |
med_6.txt | AC | 4 ms | 764 KB |
med_7.txt | AC | 3 ms | 764 KB |
med_8.txt | AC | 2 ms | 380 KB |
med_9.txt | AC | 2 ms | 636 KB |
perfect_0.txt | AC | 162 ms | 8444 KB |
perfect_1.txt | AC | 72 ms | 8828 KB |
perfect_2.txt | AC | 162 ms | 8572 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 | 3 ms | 380 KB |
small_1.txt | AC | 2 ms | 380 KB |
small_2.txt | AC | 1 ms | 256 KB |
small_3.txt | AC | 1 ms | 380 KB |
small_4.txt | AC | 3 ms | 380 KB |
small_5.txt | AC | 3 ms | 380 KB |
small_6.txt | AC | 1 ms | 380 KB |
small_7.txt | AC | 2 ms | 380 KB |
small_8.txt | AC | 3 ms | 380 KB |
small_9.txt | AC | 2 ms | 380 KB |
star_0.txt | AC | 671 ms | 78364 KB |
star_1.txt | AC | 666 ms | 78244 KB |
star_2.txt | AC | 662 ms | 78876 KB |
tencluster_0.txt | AC | 440 ms | 38384 KB |
tencluster_1.txt | AC | 439 ms | 37744 KB |
tencluster_2.txt | AC | 444 ms | 37616 KB |
tencluster_3.txt | AC | 439 ms | 38512 KB |
tencluster_4.txt | AC | 434 ms | 38512 KB |
tree_0.txt | AC | 720 ms | 76876 KB |
tree_1.txt | AC | 721 ms | 79156 KB |
tree_2.txt | AC | 710 ms | 77688 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 |