結果
問題 | No.1976 Cut then Connect |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:17:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,728 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 91,624 KB |
最終ジャッジ日時 | 2024-09-21 06:50:47 |
合計ジャッジ時間 | 4,926 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 26 |
ソースコード
import sysinput = sys.stdin.buffer.readlinesys.setrecursionlimit(10 ** 7)inf = 10 ** 9def dfs(N, root, G):que = [root]dist = [-1] * Npar = [-1] * Ndist[root] = 0while que:s = que.pop()for t in G[s]:if t == par[s]:continuepar[t] = sdist[t] = dist[s] + 1que.append(t)return dist, pardef search(N, path, G):M = len(path)res = [0] * Md = [-1] * Nfor i in range(M):ng = set()if i:ng.add(path[i-1])if i < M - 1:ng.add(path[i+1])que = [path[i]]d[path[i]] = 0while que:s = que.pop()for t in G[s]:if t in ng:continueif d[t] == -1:d[t] = d[s] + 1que.append(t)res[i] = max(res[i], d[t])return resdef calc(path, branch):M = len(path)res = []d = 0for i in range(M):d = max(d, i + branch[i])res.append((d + 1) // 2)return resN = int(input())G = [[] for _ in range(N)]for _ in range(N-1):a, b = map(int, input().split())a -= 1b -= 1G[a].append(b)G[b].append(a)r0 = 0d0, p0 = dfs(N, r0, G)r1 = d0.index(max(d0))d1, p1 = dfs(N, r1, G)r2 = d1.index(max(d1))path = [r2]while 1:x = p1[path[-1]]if x == -1:breakpath.append(x)M = len(path)dep = [min(i, M - i - 1) for i in range(M)]branch = search(N, path, G)L = calc(path, branch)R = calc(path[::-1], branch[::-1])[::-1]ans = M - 1for i in range(M - 1):ans = min(ans, L[i] + R[i+1] + 1)print(ans)