結果
問題 | No.2888 Mamehinata |
ユーザー | flippergo |
提出日時 | 2024-11-15 08:21:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 598 ms / 2,000 ms |
コード長 | 901 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 81,972 KB |
実行使用メモリ | 124,820 KB |
最終ジャッジ日時 | 2024-11-15 08:22:21 |
合計ジャッジ時間 | 17,873 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
from collections import deque N,M = map(int,input().split()) G = {i:[] for i in range(1,N+1)} for _ in range(M): a,b = map(int,input().split()) G[a].append(b) G[b].append(a) if len(G[1])==0: for i in range(1,N+1): print(0) else: dist = [-1]*(N+1) dist[1] = 0 que = deque([1]) while que: x = que.popleft() for y in G[x]: if dist[y]==-1: dist[y] = dist[x]+1 que.append(y) n = max(dist) C = {d:0 for d in range(n+1)} C[-1] = 0 for i in range(1,N+1): C[dist[i]] += 1 cnt0 = 1 cnt1 = 0 for i in range(1,N+1): if i>n:break if i%2==0: cnt0 += C[i] print(cnt0) else: cnt1 += C[i] print(cnt1) for i in range(n+1,N+1): if i%2==0: print(cnt0) else: print(cnt1)