結果
| 問題 | No.1976 Cut then Connect |
| ユーザー |
 tamato
|
| 提出日時 | 2022-06-10 22:50:57 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,171 bytes |
| コンパイル時間 | 332 ms |
| コンパイル使用メモリ | 82,288 KB |
| 実行使用メモリ | 143,144 KB |
| 最終ジャッジ日時 | 2024-09-21 06:43:37 |
| 合計ジャッジ時間 | 9,291 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 45 ms
55,704 KB |
| testcase_01 | AC | 47 ms
55,676 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | AC | 289 ms
98,952 KB |
| testcase_08 | AC | 522 ms
135,904 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 409 ms
122,084 KB |
| testcase_14 | WA | - |
| testcase_15 | AC | 390 ms
110,008 KB |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | AC | 43 ms
56,280 KB |
| testcase_23 | AC | 43 ms
55,436 KB |
| testcase_24 | AC | 44 ms
56,376 KB |
| testcase_25 | AC | 43 ms
56,604 KB |
| testcase_26 | AC | 43 ms
56,072 KB |
| testcase_27 | WA | - |
| testcase_28 | AC | 43 ms
56,740 KB |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | AC | 42 ms
55,828 KB |
ソースコード
mod = 998244353
def main():
import sys
from collections import deque
input = sys.stdin.readline
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] = 0
par = [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] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
v0 = seq[0]
que = deque()
que.append(v0)
seen = [-1] * (N+1)
seen[v0] = 0
par = [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] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
v1 = seq[0]
D = seen[v1]
if D & 1:
v = v1
for _ in range(D // 2):
v = par[v]
vl = v
vr = par[v]
vl_ori = vl
vr_ori = vr
que = deque()
que.append(vl)
seen = [-1] * (N+1)
seen[vl] = 0
par = [0] * (N+1)
child = [[] for _ in range(N+1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == vr_ori:
continue
if seen[u] == -1:
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
vl = seq[0]
que = deque()
que.append(vl)
seen = [-1] * (N + 1)
seen[vl] = 0
par = [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:
if u == vr_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
dl = seen[seq[0]]
que = deque()
que.append(vr)
seen = [-1] * (N + 1)
seen[vr] = 0
par = [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:
if u == vl_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
vr = seq[0]
que = deque()
que.append(vr)
seen = [-1] * (N + 1)
seen[vr] = 0
par = [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:
if u == vl_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
dr = seen[seq[0]]
print((dl + 1) // 2 + (dr + 1) // 2 + 1)
else:
ans = N * 2
v = v1
for _ in range(D // 2):
v = par[v]
v0 = v
que = deque()
que.append(v0)
seen = [-1] * (N+1)
seen[v0] = 0
par = [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] + 1
par[u] = v
child[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]:
cc = c
que = deque()
que.append(cc)
seen = {}
seen[cc] = 0
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == v0:
continue
if u not in seen:
seen[u] = seen[v] + 1
que.append(u)
seq.reverse()
cc = seq[0]
que = deque()
que.append(cc)
seen = {}
seen[cc] = 0
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == v0:
continue
if u not in seen:
seen[u] = seen[v] + 1
que.append(u)
seq.reverse()
dc = seen[seq[0]]
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, (dc + 1) // 2 + (dc2 + 1) // 2 + 1)
#print(cc, ans, dc, dc2)
print(ans)
#print(subtree_len)
if __name__ == '__main__':
main()