結果

問題 No.872 All Tree Path
ユーザー 6soukiti296soukiti29
提出日時 2019-08-30 23:06:55
言語 Nim
(2.0.2)
結果
AC  
実行時間 358 ms / 3,000 ms
コード長 1,261 bytes
コンパイル時間 6,034 ms
コンパイル使用メモリ 71,736 KB
実行使用メモリ 34,408 KB
最終ジャッジ日時 2023-09-15 12:45:44
合計ジャッジ時間 11,393 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 357 ms
34,204 KB
testcase_01 AC 358 ms
34,216 KB
testcase_02 AC 353 ms
34,408 KB
testcase_03 AC 209 ms
26,304 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 349 ms
34,152 KB
testcase_06 AC 354 ms
34,316 KB
testcase_07 AC 352 ms
34,404 KB
testcase_08 AC 26 ms
5,980 KB
testcase_09 AC 26 ms
6,088 KB
testcase_10 AC 27 ms
6,000 KB
testcase_11 AC 27 ms
5,932 KB
testcase_12 AC 26 ms
6,056 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils,sequtils,deques

type
    edge = tuple[R,L,w : int]
var
    N = stdin.readline.parseInt
    que = initDeque[int](1024)
    ln,rn : int
    used : array[200010, bool]
    cnt : array[200010, int]
    cnte : array[200010, int]
    edges = newSeq[edge](N)
    v,u,w : int
    nodes = newSeqWith(N + 1, newSeq[int](0))
    ans : int64

for n in 0..(N - 2):
    (v,u,w) = stdin.readline.split.map(parseInt)
    v -= 1
    u -= 1
    edges[n] = (v, u, w)
    cnte[v] += 1
    cnte[u] += 1
    nodes[v].add(n)
    nodes[u].add(n)



for n in 0..<N:
    if cnte[n] == 1:
        que.addLast(nodes[n][0])
    cnt[n] = 1

while que.len > 0:
    var e1 = que.popFirst
    if used[e1]:
        continue
    var e = edges[e1]
    used[e1] = true
    if cnte[e.R] == 1:
        ans += cnt[e.R].int64 * (N - cnt[e.R]).int64 * e.w.int64
        cnt[e.L] += cnt[e.R]
    else:
        ans += cnt[e.L].int64 * (N - cnt[e.L]).int64 * e.w.int64
        cnt[e.R] += cnt[e.L]
    cnte[e.R] -= 1
    cnte[e.L] -= 1
    if cnte[e.R] == 1:
        for t in nodes[e.R]:
            if used[t] == false:
                que.addLast(t)
    elif cnte[e.L] == 1:
        for t in nodes[e.L]:
            if used[t] == false:
                que.addLast(t)
    
echo ans * 2
0