結果
問題 | No.872 All Tree Path |
ユーザー | kept1994 |
提出日時 | 2021-09-29 01:34:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,019 ms / 3,000 ms |
コード長 | 3,394 bytes |
コンパイル時間 | 242 ms |
コンパイル使用メモリ | 87,104 KB |
実行使用メモリ | 349,364 KB |
最終ジャッジ日時 | 2023-09-22 21:38:52 |
合計ジャッジ時間 | 10,396 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 707 ms
123,636 KB |
testcase_01 | AC | 700 ms
122,700 KB |
testcase_02 | AC | 1,019 ms
125,372 KB |
testcase_03 | AC | 847 ms
349,364 KB |
testcase_04 | AC | 70 ms
71,168 KB |
testcase_05 | AC | 696 ms
124,092 KB |
testcase_06 | AC | 751 ms
126,060 KB |
testcase_07 | AC | 703 ms
124,100 KB |
testcase_08 | AC | 184 ms
85,208 KB |
testcase_09 | AC | 179 ms
85,244 KB |
testcase_10 | AC | 183 ms
85,224 KB |
testcase_11 | AC | 190 ms
84,712 KB |
testcase_12 | AC | 178 ms
84,856 KB |
testcase_13 | AC | 69 ms
71,180 KB |
testcase_14 | AC | 70 ms
70,920 KB |
testcase_15 | AC | 71 ms
71,348 KB |
testcase_16 | AC | 71 ms
71,332 KB |
testcase_17 | AC | 71 ms
71,312 KB |
testcase_18 | AC | 71 ms
71,368 KB |
testcase_19 | AC | 71 ms
71,376 KB |
ソースコード
#!/usr/bin/env python3 import sys def solve(N: int, u: "List[int]", v: "List[int]", c): sys.setrecursionlimit(10 ** 9) partTreeSize = [1] * N ans = 0 class DFS(): def __init__(self, N: int) -> None: self.nodes = N # 頂点数 self.G = [[] for _ in range(N)] # グラフ self.seen = [False] * N # 各ノードが訪問済みかどうかのフラグ # self.firstOrder = [] # ノードの行きがけ順(0-index) # self.lastOrder = [] # ノードの帰りがけ順(0-index) # 辺の追加 def addEdge(self, fromNode: int, toNode: int, cost: int, bothDirection: bool): self.G[fromNode].append((toNode, cost)) if bothDirection: self.G[toNode].append((fromNode, cost)) # DFS def build(self, now: int, depth:int): # ----- ノードに到着した時の処理 # self.firstOrder.append(now) self.seen[now] = True # ----- 隣接する各ノードへの移動処理 for next in self.G[now]: if self.seen[next[0]]: continue # -- 隣接ノードに行く時 # -- 移動処理 -- self.build(next[0], depth + 1) # -- 隣接ノードから戻ってきた時 partTreeSize[now] += partTreeSize[next[0]] # ----- ノードから戻る時の処理 # self.lastOrder.append(now) return def build2(self, now: int): nonlocal ans # ----- ノードに到着した時の処理 # self.firstOrder.append(now) self.seen[now] = True # ----- 隣接する各ノードへの移動処理 for next in self.G[now]: if self.seen[next[0]]: continue # -- 隣接ノードに行く時 # ans[next[0]] = ans[now] - partTreeSize[next[0]] + (N - partTreeSize[next[0]]) # -- 移動処理 -- self.build2(next[0]) # -- 隣接ノードから戻ってきた時 ans += partTreeSize[next[0]] * (self.nodes - partTreeSize[next[0]]) * next[1] # ----- ノードから戻る時の処理 # self.lastOrder.append(now) return d = DFS(N) for uu, vv, cc in zip(u, v, c): d.addEdge(uu - 1, vv - 1, cc, bothDirection=True) d.build(0, 0) d.seen = [False] * N d.build2(0) print(ans * 2) return # Generated by 2.8.0 https://github.com/kyuridenamida/atcoder-tools (tips: You use the default template now. You can remove this line by using your custom template) def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() N = int(next(tokens)) # type: int u = [int()] * (N - 1) # type: "List[int]" v = [int()] * (N - 1) # type: "List[int]" c = [int()] * (N - 1) # type: "List[int]" for i in range(N - 1): u[i] = int(next(tokens)) v[i] = int(next(tokens)) c[i] = int(next(tokens)) solve(N, u, v, c) if __name__ == '__main__': main()