Submission #3418431


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

import sequtils,sets,math
type
  Edge* = object
    to : int
  Graph*[E] = object
    edges : seq[seq[Edge]]
    n : int

proc newGraph*[E](n : int) : Graph[E] =
  var g : Graph[E]
  g.edges = newSeqWith(n , newSeq[E](0))
  g.n = n
  return g

proc `[]`*[E](g : var Graph[E] , k : int) : var seq[Edge] =
  return g.edges[k]

proc lowlink*[E](g : Graph[E]) : seq[tuple[a : int , b : int]] =
  var 
    bridge : seq[tuple[a : int , b : int]] = @[]
    n = g.n
    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.edges[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 twoEdgeConnectedComponent*[E](g : Graph[E]) : tuple[cmp : seq[int] , tree : Graph[E]] =
  var
    bridge = g.lowlink
    st = initIntSet()
    n = g.n
    cmp = newSeqWith(n , -1)
    dfs : proc(v , f , k : int)
    k = 0
  for b in bridge: st.incl(b.a * g.n + b.b)
  dfs = proc(v,f,k : int) =
    cmp[v] = k
    for e in g.edges[v]:
      if cmp[e.to] == -1 and not st.contains(min(v,e.to) * g.n + 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.n
  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.edges[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.twoEdgeConnectedComponent
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 4107 Byte
Status AC
Exec Time 787 ms
Memory 87844 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(22, 10) Hint: 'E' is declared but not used [XDeclaredButNotUsed]
Main.nim(15, 6) Hint: 'Main.gf()' is declared but not used [XDeclaredButNotUsed]
Hint:  [Link]
Hint: operation successful (25595 lines compiled; 2.610 sec total; 26.266MB; Release Build) [SuccessX]

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 80
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 392 ms 46576 KB
bigcycleandsub_1.txt AC 392 ms 46576 KB
cluster_0.txt AC 446 ms 33648 KB
cluster_1.txt AC 445 ms 33904 KB
cluster_2.txt AC 440 ms 33392 KB
cluster_3.txt AC 444 ms 33776 KB
cluster_4.txt AC 452 ms 33520 KB
cycleline_0.txt AC 442 ms 32624 KB
cycleline_1.txt AC 449 ms 32624 KB
cycleline_2.txt AC 451 ms 32368 KB
cycleline_3.txt AC 455 ms 32496 KB
cycleline_4.txt AC 446 ms 32880 KB
cycletree_0.txt AC 451 ms 32240 KB
cycletree_1.txt AC 445 ms 32112 KB
cycletree_2.txt AC 454 ms 32112 KB
cycletree_3.txt AC 451 ms 32368 KB
cycletree_4.txt AC 467 ms 32368 KB
large_0.txt AC 390 ms 36412 KB
large_1.txt AC 81 ms 5628 KB
large_2.txt AC 276 ms 33404 KB
line_0.txt AC 577 ms 87844 KB
line_1.txt AC 390 ms 85808 KB
lineandsub_0.txt AC 751 ms 83348 KB
lineandsub_1.txt AC 723 ms 86972 KB
lineandsub_2.txt AC 748 ms 86068 KB
maxrand_0.txt AC 445 ms 42736 KB
maxrand_1.txt AC 463 ms 42736 KB
maxrand_2.txt AC 452 ms 42736 KB
maxrandandsub_0.txt AC 472 ms 49904 KB
maxrandandsub_1.txt AC 478 ms 49904 KB
maxrandandsub_2.txt AC 471 ms 49904 KB
maxrandandsub_3.txt AC 476 ms 49648 KB
maxrandandsub_4.txt AC 506 ms 49904 KB
med_0.txt AC 4 ms 636 KB
med_1.txt AC 3 ms 380 KB
med_2.txt AC 3 ms 636 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 165 ms 8316 KB
perfect_1.txt AC 77 ms 8700 KB
perfect_2.txt AC 165 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 749 ms 77400 KB
star_1.txt AC 726 ms 73676 KB
star_2.txt AC 766 ms 76300 KB
tencluster_0.txt AC 444 ms 34672 KB
tencluster_1.txt AC 442 ms 34160 KB
tencluster_2.txt AC 440 ms 33904 KB
tencluster_3.txt AC 444 ms 34928 KB
tencluster_4.txt AC 441 ms 34800 KB
tree_0.txt AC 774 ms 75964 KB
tree_1.txt AC 787 ms 74328 KB
tree_2.txt AC 781 ms 75556 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