結果
問題 | No.872 All Tree Path |
ユーザー | ningenMe |
提出日時 | 2019-08-29 23:48:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,680 ms / 3,000 ms |
コード長 | 775 bytes |
コンパイル時間 | 643 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 159,808 KB |
最終ジャッジ日時 | 2024-04-28 23:00:22 |
合計ジャッジ時間 | 15,614 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,625 ms
159,104 KB |
testcase_01 | AC | 1,546 ms
159,232 KB |
testcase_02 | AC | 1,680 ms
159,364 KB |
testcase_03 | AC | 548 ms
155,264 KB |
testcase_04 | AC | 74 ms
67,072 KB |
testcase_05 | AC | 1,633 ms
159,508 KB |
testcase_06 | AC | 1,664 ms
158,720 KB |
testcase_07 | AC | 1,612 ms
159,808 KB |
testcase_08 | AC | 259 ms
87,040 KB |
testcase_09 | AC | 262 ms
86,784 KB |
testcase_10 | AC | 268 ms
86,784 KB |
testcase_11 | AC | 269 ms
86,400 KB |
testcase_12 | AC | 271 ms
86,656 KB |
testcase_13 | AC | 75 ms
66,816 KB |
testcase_14 | AC | 75 ms
67,072 KB |
testcase_15 | AC | 75 ms
66,944 KB |
testcase_16 | AC | 73 ms
67,200 KB |
testcase_17 | AC | 75 ms
67,200 KB |
testcase_18 | AC | 75 ms
67,200 KB |
testcase_19 | AC | 75 ms
67,200 KB |
ソースコード
import queue N = int(input()) edge = [[] for i in range(N)] size = [1 for i in range(N)] depth = [[-1,i] for i in range(N)] parent = [-1 for i in range(N)] dist = [0 for i in range(N)] for i in range(N-1): u,v,w = map(int,input().split()) u-=1 v-=1 edge[u].append([v,w]) edge[v].append([u,w]) q = queue.Queue() q.put(0) depth[0] = [0,0] while q.qsize() > 0: f = q.get() for t,w in edge[f]: if depth[t][0] == -1: depth[t][0] = depth[f][0] + 1 dist[t] = dist[f] + w parent[t] = f q.put(t) depth.sort(reverse=True) ans = 0 for tmp,i in depth: if parent[i] != -1: M = size[i] size[parent[i]] += M d = dist[i] - dist[parent[i]] ans += 2*M*(N-M)*d print(ans)