結果

問題 No.922 東北きりきざむたん
ユーザー nadeshinonadeshino
提出日時 2019-11-11 00:53:30
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,202 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 71,104 KB
最終ジャッジ日時 2024-11-14 21:50:07
合計ジャッジ時間 2,576 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 19) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
stack trace: (most recent call last)
Main.nim(6, 9)           unpack
/home/judge/data/code/Main.nim(123, 24) template/generic instantiation of `input` from here
/home/judge/data/code/Main.nim(12, 44) template/generic instantiation of `unpack` from here
/home/judge/data/code/Main.nim(6, 9) Error: index 1 not in 0 .. 0

ソースコード

diff # 

import algorithm, future, macros, math, sequtils, sets, strutils, tables

macro unpack(rhs: seq, cnt: static[int]): auto =
  let v = genSym(); result = quote do:(let `v` = `rhs`;())
  if NimMinor <= 17:
    for i in 0..<cnt: result[0][1].add(quote do:`v`[`i`])
  else:
    for i in 0..<cnt: result[1].add(quote do:`v`[`i`])

template input(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseint)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc `<?=`(n: var SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))

# -------------------------------------------------- #

type UnionFind = object
  data: seq[int]

proc initUnionFind(N: int): UnionFind =
  result.data = newSeqWith(N + 1, -1)

proc find(this: var UnionFind, v: int): int =
  if this.data[v] < 0:
    return v
  this.data[v] = this.find(this.data[v])
  return this.data[v]

proc unite(this: var UnionFind, u, v: int) =
  var u = this.find(u)
  var v = this.find(v)
  if u == v:
    return
  if this.data[u] < this.data[v]:
    swap(u, v)
  this.data[v] += this.data[u]
  this.data[u] = v

proc same(this: var UnionFind, u, v: int): bool =
  return this.find(u) == this.find(v)

proc size(this: var UnionFind, v: int): int =
  return -this.data[this.find(v)]

# -------------------------------------------------- #

type LowestCommonAncestor = object
  size: int
  root: int
  edges: seq[seq[int]]
  parent: seq[seq[int]]
  depth: seq[int]

proc initLowestCommonAncestor(N: int, root: int): LowestCommonAncestor =
  let logN = log2(N.float).int
  result.size = N
  result.root = root
  result.edges = newSeqWith(N + 1, newSeq[int](0))
  result.parent = newSeqWith(logN + 1, newSeq[int](N + 1))
  result.depth = newSeq[int](N + 1)

proc dfs(self: var LowestCommonAncestor, v: int, p: int, d: int) =
  self.parent[0][v] = p
  self.depth[v] = d
  for u in self.edges[v]:
    if u != p:
      dfs(self, u, v, d + 1)

proc build(self: var LowestCommonAncestor) =
  let N = self.size
  let logN = log2(N.float).int
  self.dfs(self.root, -1, 0)
  for k in 1 .. logN:
    for v in 1 .. N:
      if self.parent[k - 1][v] == -1:
        self.parent[k][v] = -1
      else:
        self.parent[k][v] = self.parent[k - 1][self.parent[k - 1][v]]

proc addEdge(self: var LowestCommonAncestor, v: int, u: int) =
  self.edges[v].add(u)
  self.edges[u].add(v)

proc lca(self: var LowestCommonAncestor, v: int, u: int): int =
  var built {.global.} = false
  if not built:
    self.build()
    built = true

  var (v, u) = (v, u)
  let logN = log2(self.size.float).int
  if self.depth[v] > self.depth[u]:
    swap(v, u)
  for k in 0 .. logN:
    if (((self.depth[u] - self.depth[v]) shr k) and 1) == 1:
      u = self.parent[k][u]
  if v == u:
    return v
  for k in countdown(logN, 0):
    if self.parent[k][v] != self.parent[k][u]:
      v = self.parent[k][v]
      u = self.parent[k][u]
  return self.parent[0][v]

proc distance(self: var LowestCommonAncestor, v: int, u: int): int =
  let lca = self.lca(v, u)
  return self.depth[v] + self.depth[u] - 2 * self.depth[lca]

# -------------------------------------------------- #

proc main =
  var (N, M, Q) = input(int, 3)
  var union = initUnionFind(N)
  var tree = initLowestCommonAncestor(N, 0)
  var edges = newseq2[int](N + 1, 0)
  for _ in 1 .. M:
    var (u, v) = input(int, 2)
    union.unite(u, v)
    tree.addEdge(u, v)
    edges[u].add(v)
    edges[v].add(u)

  var queries = newseq[tuple[a: int, b: int]](Q)
  var size = newseq[int](N + 1)
  for i in 0 ..< Q:
    var (a, b) = input(int, 2)
    queries[i] = (a, b)
    if not union.same(a, b):
      inc size[a]; inc size[b]

  var centroids = inittable[int, int]()
  block findCentroids:
    var sum = 0
    proc preCalc(v: int, p: int) =
      sum += size[v]
      for u in edges[v]:
        if u != p:
          preCalc(u, v)

    var used = newseq[bool](N + 1)
    var centroid: int
    proc dfs(v: int, p: int) =
      used[v] = true
      var isCentroid = true
      for u in edges[v]:
        if u == p: continue
        dfs(u, v)
        if size[u] > sum div 2:
          isCentroid = false
        size[v] += size[u]
      if sum - size[v] > sum div 2:
        isCentroid = false
      if isCentroid:
        centroid = v

    for v in 1 .. N:
      if used[v]: continue
      sum = 0
      preCalc(v, -1)
      dfs(v, -1)
      centroids[union.find(v)] = centroid
      tree.addEdge(v, 0)
  
  var res = 0
  for q in queries:
    var (a, b) = q
    if union.same(a, b):
      res += tree.distance(a, b)
    else:
      res += tree.distance(a, centroids[union.find(a)])
      res += tree.distance(b, centroids[union.find(b)])
  
  echo res

main()
0