結果

問題 No.386 貪欲な領主
ユーザー むらため
提出日時 2019-02-04 03:50:45
言語 Nim
(2.2.0)
結果
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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0