結果

問題 No.386 貪欲な領主
ユーザー むらためむらため
提出日時 2019-02-04 03:50:45
言語 Nim
(2.0.2)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 2,775 bytes
コンパイル時間 2,709 ms
コンパイル使用メモリ 63,276 KB
実行使用メモリ 53,696 KB
最終ジャッジ日時 2024-07-01 11:19:52
合計ジャッジ時間 5,191 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 219 ms
53,404 KB
testcase_05 AC 154 ms
43,312 KB
testcase_06 AC 168 ms
43,720 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 18 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 5 ms
6,944 KB
testcase_14 AC 172 ms
42,976 KB
testcase_15 AC 215 ms
53,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sequtils,bitops
template times*(n:int,body) = (for _ in 0..<n: body)

# (親も子も同一視して)双方向になっている木を,0 番を根として子のノードだけ持つように変更する
proc deleteParent(E:seq[seq[int]]):seq[seq[int]] =
  var answer = newSeqWith(E.len,newSeq[int]())
  proc impl(pre,now:int) =
    for dst in E[now]:
      if dst == pre : continue
      answer[now] &= dst
      impl(now,dst)
  impl(-1,0)
  return answer

# 最小共通祖先 構築:O(n),探索:O(log(n)) (深さに依存しない)
type LowestCommonAncestor = ref object
  depth : seq[int]
  parent : seq[seq[int]] # 2^k 回親をたどった時のノード
  n:int
  nlog2 : int
proc initLowestCommonAnsestor(E:seq[seq[int]],root:int = 0) : LowestCommonAncestor =
  new(result)
  # E:隣接リスト,root:根の番号,(0~E.len-1と仮定)
  # (import bitops)
  # 予め木を整形(= E[i]で親と子の区別を行う)する必要はない
  let n = E.len
  let nlog2 = E.len.fastLog2() + 1
  var depth = newSeq[int](n)
  var parent = newSeqWith(nlog2,newSeq[int](E.len))
  proc fill0thParent(src,pre,currentDepth:int) =
    parent[0][src] = pre
    depth[src] = currentDepth
    for dst in E[src]:
      if dst != pre : fill0thParent(dst,src,currentDepth+1)
  fill0thParent(root,-1,0)
  for k in 0..<nlog2-1:
    for v in 0..<n:
      if parent[k][v] < 0 : parent[k+1][v] = -1
      else: parent[k+1][v] = parent[k][parent[k][v]]
  result.depth = depth
  result.parent = parent
  result.n = n
  result.nlog2 = nlog2
proc find(self:LowestCommonAncestor,u,v:int):int =
  var (u,v) = (u,v)
  if self.depth[u] > self.depth[v] : swap(u,v)
  for k in 0..<self.nlog2:
    if (((self.depth[v] - self.depth[u]) shr k) and 1) != 0 :
      v = self.parent[k][v]
  if u == v : return u
  for k in (self.nlog2-1).countdown(0):
    if self.parent[k][u] == self.parent[k][v] : continue
    u = self.parent[k][u]
    v = self.parent[k][v]
  return self.parent[0][u]

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': return
    result = 10 * result + k.ord - '0'.ord

# 木を造って根からの距離を保持してLCA分引く
let n = scan()
var E = newSeqWith(n,newSeq[int]())
(n-1).times:
  let u = scan()
  let v = scan()
  E[u] &= v
  E[v] &= u
E = E.deleteParent()
let lca = E.initLowestCommonAnsestor()
let C = newSeqWith(n,scan()) # cost
var C0 = newSeqWith(n,-1) # 0 からのcost
proc fillFrom0(i,c:int) =
  C0[i] = C[i] + c
  for dst in E[i]: fillFrom0(dst,C0[i])
fillFrom0(0,0)
var ans = 0
scan().times:
  let u = scan()
  let v = scan()
  let c = scan()
  let parent = lca.find(u,v)
  ans += (C0[u] + C0[v] - 2 * C0[parent] + C[parent]) * c
echo ans
0