結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2023-01-15 13:02:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 358 ms / 3,000 ms |
コード長 | 1,372 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 102,016 KB |
最終ジャッジ日時 | 2024-12-28 03:37:58 |
合計ジャッジ時間 | 6,005 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from typing import List, Tuple, Callable, TypeVar, Optionalimport sysimport itertoolsimport heapqimport bisectimport mathfrom collections import deque, defaultdictfrom functools import lru_cache, cmp_to_keyinput = sys.stdin.readlineif __file__ != 'prog.py':sys.setrecursionlimit(10 ** 6)def readints(): return map(int, input().split())def readlist(): return list(readints())def readstr(): return input()[:-1]def readlist1(): return list(map(lambda x: int(x) - 1, input().split()))N = int(input())E = [[] for _ in range(N)]for _ in range(N - 1):u, v = readints()u -= 1v -= 1E[u].append(v)E[v].append(u)R = [0] * Nis_leaf = [True] * Nstack = [(0, -1)]while stack:v, p = stack.pop()if v < 0:v = ~vfor dst in E[v]:if dst == p:continueis_leaf[v] = Falseelse:if ~p:R[v] = R[p] + 1stack.append((~v, p))for dst in E[v]:if dst == p:continuestack.append((dst, v))INF = 1 << 30L = [INF] * Ndq = deque()for i in range(N):if is_leaf[i]:L[i] = 0dq.append(i)while dq:v = dq.popleft()for dst in E[v]:if L[dst] > L[v] + 1:L[dst] = L[v] + 1dq.append(dst)for r, l in zip(R, L):print(min(r, l))