結果

問題 No.386 貪欲な領主
ユーザー むらためむらため
提出日時 2019-02-05 13:39:12
言語 Nim
(2.0.0)
結果
AC  
実行時間 507 ms / 2,000 ms
コード長 1,053 bytes
コンパイル時間 3,520 ms
コンパイル使用メモリ 71,628 KB
実行使用メモリ 81,896 KB
最終ジャッジ日時 2023-09-14 03:33:13
合計ジャッジ時間 6,939 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 432 ms
81,556 KB
testcase_05 AC 357 ms
69,400 KB
testcase_06 AC 408 ms
68,956 KB
testcase_07 AC 5 ms
4,376 KB
testcase_08 AC 54 ms
8,944 KB
testcase_09 AC 8 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 12 ms
4,624 KB
testcase_14 AC 507 ms
68,732 KB
testcase_15 AC 501 ms
81,896 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 8) Warning: Deprecated since v1.5; Use auto instead.; any is deprecated [Deprecated]
/home/judge/data/code/Main.nim(3, 8) Warning: Deprecated since v1.5; Use auto instead.; any is deprecated [Deprecated]

ソースコード

diff #

import sequtils,bitops,strutils
proc r:any=stdin.readLine.parseInt
proc R:any=stdin.readLine.split.map parseInt
var
 n=r()
 E=newSeqWith n:newSeq[int]()
 A=E
 o:tuple[d:seq[int],p:seq[seq[int]],n,m:int]
for _ in 0..<n-1:(let t=R();E[t[0]]&=t[1];E[t[1]]&=t[0])
proc i(e,w:int)=(for t in E[w]:(if t!=e:(A[w]&=t;i(w,t))))
i(-1,0)
E=A
block:
 var
  m=n.fastLog2+1
  d=newSeq[int]n
  p=newSeqWith m:newSeq[int]n
 proc fp(s,e,cd:int)=(p[0][s]=e;d[s]=cd;for t in E[s]:(if t!=e:fp t,s,cd+1))
 fp 0,-1,0
 for k in 0..<m-1:(for v in 0..<n:(if p[k][v]<0:p[k+1][v]= -1 else:p[k+1][v]=p[k][p[k][v]]))
 o=(d,p,n,m)
var
 C=newSeqWith n:r()
 I=newSeqWith n: -1
 a=0
proc x(u,v:int):int=
 var(u,v)=(u,v)
 if o.d[u]>o.d[v]:swap u,v
 for k in 0..<o.m:(if(((o.d[v]-o.d[u])shr k)and 1)!=0:v=o.p[k][v])
 if u==v:return u
 for k in(o.m-1).countdown(0):(if o.p[k][u]!=o.p[k][v]:(u=o.p[k][u];v=o.p[k][v]))
 return o.p[0][u]
proc ff(i,c:int)=(I[i]=C[i]+c;for t in E[i]:ff t,I[i])
ff 0,0
for _ in 0..<r():(let t=R();let p=x(t[0],t[1]);a+=(I[t[0]]+I[t[1]]-2*I[p]+C[p])*t[2])
echo a
0