結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
![]() |
提出日時 | 2022-11-30 23:27:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 915 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 103,652 KB |
最終ジャッジ日時 | 2024-10-07 18:52:15 |
合計ジャッジ時間 | 5,007 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
from collections import deque N = int(input()) G = [list() for _ in range(N)] for i in range(N-1): a, b = map(int, input().split()) a-=1;b-=1 G[a].append(b) G[b].append(a) s1, s2 = [], [] for i in range(N): if len(G[i])==1: s1.append(i) else: s2.append(i) if len(s1)==2: exit(print('Yes')) else: cnt = 0 s3 = [] for s in s2: if len(G[s])>=3: cnt += 1 s3.append(s) if cnt>1: exit(print('No')) else: d = deque([s3[0]]) dis = [-1]*N dis[s3[0]] = 0 while d: v = d.popleft() for nex in G[v]: if dis[nex]==-1: dis[nex]= dis[v]+1 d.append(nex) dd = [] for a in s1: dd.append(dis[a]) if len(set(dd))==1: print('Yes') else: print('No')