結果
問題 | No.1817 Reversed Edges |
ユーザー |
|
提出日時 | 2022-01-21 22:05:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 720 ms / 2,000 ms |
コード長 | 886 bytes |
コンパイル時間 | 215 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 34,668 KB |
最終ジャッジ日時 | 2024-11-26 00:18:27 |
合計ジャッジ時間 | 12,569 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
from collections import deque N = int(input()) G = [[] for _ in range(N)] for _ in range(N - 1): u, v = map(lambda x: int(x) - 1, input().split()) G[u].append(v) G[v].append(u) que = deque([0]) visited = [False] * N visited[0] = True cost = [0] * N while que: node = que.popleft() nears = G[node] for near in nears: if visited[near]: continue if near < node: cost[0] += 1 visited[near] = True que.append(near) que = deque([0]) visited = [False] * N visited[0] = True while que: node = que.popleft() nears = G[node] for near in nears: if visited[near]: continue cost[near] = cost[node] if near > node: cost[near] += 1 else: cost[near] -= 1 visited[near] = True que.append(near) print(*cost, sep="\n")