結果
問題 | No.1424 Ultrapalindrome |
ユーザー | H3PO4 |
提出日時 | 2022-07-07 22:54:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,277 bytes |
コンパイル時間 | 672 ms |
コンパイル使用メモリ | 87,264 KB |
実行使用メモリ | 96,808 KB |
最終ジャッジ日時 | 2023-08-26 13:48:40 |
合計ジャッジ時間 | 9,870 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 94 ms
71,660 KB |
testcase_01 | AC | 93 ms
71,596 KB |
testcase_02 | AC | 92 ms
71,448 KB |
testcase_03 | AC | 92 ms
71,600 KB |
testcase_04 | AC | 90 ms
71,600 KB |
testcase_05 | AC | 92 ms
71,716 KB |
testcase_06 | AC | 91 ms
71,884 KB |
testcase_07 | WA | - |
testcase_08 | AC | 92 ms
71,596 KB |
testcase_09 | AC | 325 ms
90,312 KB |
testcase_10 | AC | 347 ms
92,400 KB |
testcase_11 | AC | 215 ms
86,044 KB |
testcase_12 | AC | 248 ms
88,496 KB |
testcase_13 | AC | 155 ms
81,684 KB |
testcase_14 | AC | 239 ms
87,776 KB |
testcase_15 | AC | 97 ms
77,008 KB |
testcase_16 | AC | 208 ms
84,748 KB |
testcase_17 | AC | 214 ms
85,848 KB |
testcase_18 | AC | 205 ms
84,384 KB |
testcase_19 | AC | 273 ms
88,120 KB |
testcase_20 | AC | 145 ms
80,240 KB |
testcase_21 | AC | 219 ms
85,160 KB |
testcase_22 | AC | 176 ms
82,640 KB |
testcase_23 | AC | 121 ms
78,292 KB |
testcase_24 | AC | 146 ms
79,888 KB |
testcase_25 | AC | 147 ms
79,632 KB |
testcase_26 | AC | 315 ms
88,016 KB |
testcase_27 | AC | 414 ms
96,808 KB |
testcase_28 | AC | 147 ms
87,192 KB |
testcase_29 | AC | 193 ms
94,992 KB |
testcase_30 | AC | 189 ms
95,376 KB |
testcase_31 | AC | 184 ms
94,884 KB |
ソースコード
import sys from collections import deque input = sys.stdin.buffer.readline def bfs(N, T, s, return_all_dist=False): dist = [None] * N dist[s] = 0 d = deque([s]) while d: v = d.popleft() dx = dist[v] + 1 for x in T[v]: if dist[x] is not None: continue dist[x] = dx d.append(x) if return_all_dist: return dist else: max_dist = max(dist) return dist.index(max_dist), max_dist def med_tree(N, T): u, _ = bfs(N, T, 0) v, max_dist = bfs(N, T, u) if max_dist % 2: return None med_dist = max_dist // 2 dist_u = bfs(N, T, u, return_all_dist=True) dist_v = bfs(N, T, v, return_all_dist=True) for i, (du, dv) in enumerate(zip(dist_u, dist_v)): if du == dv == med_dist: return i def solve(N, T): leaves_num = sum([len(t) == 1 for t in T]) if leaves_num == 2: # 直線 return True med = med_tree(N, T) if med is None: return False return len(T[med]) == leaves_num N = int(input()) T = [[] for _ in range(N)] for _ in range(N - 1): a, b = (int(x) - 1 for x in input().split()) T[a].append(b) T[b].append(a) print("Yes" if solve(N, T) else "No")