結果
問題 | No.1976 Cut then Connect |
ユーザー | tktk_snsn |
提出日時 | 2022-06-10 23:59:14 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 1,769 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 86,676 KB |
実行使用メモリ | 92,364 KB |
最終ジャッジ日時 | 2023-08-16 02:42:50 |
合計ジャッジ時間 | 5,774 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,140 KB |
testcase_01 | AC | 68 ms
71,296 KB |
testcase_02 | AC | 197 ms
91,724 KB |
testcase_03 | AC | 143 ms
84,284 KB |
testcase_04 | AC | 110 ms
80,388 KB |
testcase_05 | AC | 134 ms
83,648 KB |
testcase_06 | AC | 158 ms
88,572 KB |
testcase_07 | AC | 131 ms
83,684 KB |
testcase_08 | AC | 204 ms
92,236 KB |
testcase_09 | AC | 177 ms
90,192 KB |
testcase_10 | AC | 109 ms
81,028 KB |
testcase_11 | AC | 198 ms
91,984 KB |
testcase_12 | AC | 88 ms
76,676 KB |
testcase_13 | AC | 164 ms
88,580 KB |
testcase_14 | AC | 154 ms
85,116 KB |
testcase_15 | AC | 155 ms
87,320 KB |
testcase_16 | AC | 179 ms
91,028 KB |
testcase_17 | AC | 116 ms
82,440 KB |
testcase_18 | AC | 91 ms
76,640 KB |
testcase_19 | AC | 172 ms
88,588 KB |
testcase_20 | AC | 208 ms
92,364 KB |
testcase_21 | AC | 145 ms
84,432 KB |
testcase_22 | AC | 70 ms
71,352 KB |
testcase_23 | AC | 70 ms
71,268 KB |
testcase_24 | AC | 69 ms
71,296 KB |
testcase_25 | AC | 70 ms
71,172 KB |
testcase_26 | AC | 69 ms
71,128 KB |
testcase_27 | AC | 70 ms
70,928 KB |
testcase_28 | AC | 71 ms
71,348 KB |
testcase_29 | AC | 71 ms
71,348 KB |
testcase_30 | AC | 71 ms
71,292 KB |
testcase_31 | AC | 69 ms
71,300 KB |
testcase_32 | AC | 68 ms
71,372 KB |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) inf = 10 ** 9 def dfs(N, root, G): que = [root] dist = [-1] * N par = [-1] * N dist[root] = 0 while que: s = que.pop() for t in G[s]: if t == par[s]: continue par[t] = s dist[t] = dist[s] + 1 que.append(t) return dist, par def search(N, path, G): M = len(path) res = [0] * M d = [-1] * N for 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]] = 0 while que: s = que.pop() for t in G[s]: if t in ng: continue if d[t] == -1: d[t] = d[s] + 1 que.append(t) res[i] = max(res[i], d[t]) return res def calc(path, branch): M = len(path) res = [] d = 0 for i in range(M): d = max(d, i + branch[i]) res.append(d) return res N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) r0 = 0 d0, 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: break path.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 = inf for i in range(M - 1): l = L[i] r = R[i+1] d = max(l, r, (l+1)//2 + (r+1)//2 + 1) ans = min(ans, d) print(ans)