結果
問題 |
No.277 根掘り葉掘り
|
ユーザー |
👑 |
提出日時 | 2022-07-14 13:57:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 284 ms / 3,000 ms |
コード長 | 803 bytes |
コンパイル時間 | 912 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 98,352 KB |
最終ジャッジ日時 | 2024-06-25 21:14:36 |
合計ジャッジ時間 | 5,417 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import deque n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): u, v = map(int, input().split()) u -= 1 v -= 1 edges[u].append(v) edges[v].append(u) queue = deque() queue.append(0) R = [-1] * n R[0] = 0 leaf = [] while queue: pos = queue.popleft() le = True for npos in edges[pos]: if R[npos] != -1: continue le = False R[npos] = R[pos] + 1 queue.append(npos) if le: leaf.append(pos) queue = deque() L = [-1] * n for l in leaf: L[l] = 0 queue.append(l) while queue: pos = queue.popleft() for npos in edges[pos]: if L[npos] != -1: continue L[npos] = L[pos] + 1 queue.append(npos) for l, r in zip(L, R): print(min(l, r))