結果
問題 | No.1976 Cut then Connect |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:09:28 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,785 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 138,668 KB |
最終ジャッジ日時 | 2024-09-21 06:48:46 |
合計ジャッジ時間 | 7,689 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 1 |
other | AC * 11 WA * 7 RE * 13 |
ソースコード
mod = 998244353def main():import sysfrom collections import dequeinput = sys.stdin.readlinedef radius(v0, v1):que = deque()que.append(v0)seen = {}seen[v0] = 0v_last = 0while que:v = que.popleft()for u in adj[v]:if u == v1:continueif u not in seen:seen[u] = seen[v] + 1que.append(u)v_last = vv0 = v_lastque = deque()que.append(v0)seen = {}seen[v0] = 0v_last = 0while que:v = que.popleft()for u in adj[v]:if u == v1:continueif u not in seen:seen[u] = seen[v] + 1que.append(u)v_last = vreturn seen[v_last]N = int(input())adj = [[] for _ in range(N + 1)]for _ in range(N - 1):a, b = map(int, input().split())adj[a].append(b)adj[b].append(a)que = deque()que.append(1)seen = [-1] * (N+1)seen[1] = 0par = [0] * (N+1)child = [[] for _ in range(N+1)]seq = []while que:v = que.popleft()seq.append(v)for u in adj[v]:if seen[u] == -1:seen[u] = seen[v] + 1par[u] = vchild[v].append(u)que.append(u)seq.reverse()v0 = seq[0]que = deque()que.append(v0)seen = [-1] * (N+1)seen[v0] = 0par = [0] * (N+1)child = [[] for _ in range(N+1)]seq = []while que:v = que.popleft()seq.append(v)for u in adj[v]:if seen[u] == -1:seen[u] = seen[v] + 1par[u] = vchild[v].append(u)que.append(u)seq.reverse()v1 = seq[0]D = seen[v1]if D & 1:v = v1for _ in range(D // 2):v = par[v]vl = vvr = par[v]dl = radius(vl, vr)dr = radius(vr, vl)print(max((dl + 1) // 2 + (dr + 1) // 2 + 1, dl, dr))assert Falseelse:ans = N * 2v = v1for _ in range(D // 2):v = par[v]v0 = vque = deque()que.append(v0)seen = [-1] * (N+1)seen[v0] = 0par = [0] * (N+1)child = [[] for _ in range(N+1)]seq = []while que:v = que.popleft()seq.append(v)for u in adj[v]:if seen[u] == -1:seen[u] = seen[v] + 1par[u] = vchild[v].append(u)que.append(u)seq.reverse()subtree_len = [(0, 0)]for c in child[v0]:que = deque()seq = []que.append(c)while que:v = que.popleft()for vv in child[v]:que.append(vv)seq.append(v)subtree_len.append((seen[seq[-1]], c))subtree_len.sort(key=lambda x: x[0], reverse=True)for c in child[v0]:dc = radius(c, v0)if c == subtree_len[0][1]:dc2 = subtree_len[1][0] + subtree_len[2][0]elif c == subtree_len[1][1]:dc2 = subtree_len[0][0] + subtree_len[2][0]else:dc2 = subtree_len[0][0] + subtree_len[1][0]ans = min(ans, max((dc + 1) // 2 + (dc2 + 1) // 2 + 1, dc, dc2))#print(cc, ans, dc, dc2)print(ans)#print(subtree_len)if __name__ == '__main__':main()