結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
![]() |
提出日時 | 2023-03-01 23:24:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 970 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 109,096 KB |
最終ジャッジ日時 | 2024-09-16 20:33:11 |
合計ジャッジ時間 | 5,282 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys readline = sys.stdin.readline from collections import deque N = int(readline()) G = [[] for i in range(N)] D = [0] * N for i in range(N - 1): A, B = map(int, readline().split()) A, B = A - 1, B - 1 G[A].append(B) G[B].append(A) D[A] += 1 D[B] += 1 Q = deque() dist = dict() for i in range(N): dist[i] = -1 par = [-1] * N cnt = N for i in range(N): if D[i] == 1: Q.append(i) dist[i] = 0 cnt -= 1 if D.count(1) == 2 and D.count(2) == N - 2: print("Yes") exit() while Q: u = Q.popleft() # print(u, dist, Q) for v in G[u]: if v == par[u]: continue if dist[v] != -1: if cnt: print("No") exit() if dist[v] == dist[u]: print("No") exit() continue dist[v] = dist[u] + 1 par[v] = u cnt -= 1 Q.append(v) print("Yes")