結果

問題 No.2888 Mamehinata
コンテスト
ユーザー PNJ
提出日時 2024-09-13 23:43:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 701 ms / 2,000 ms
コード長 815 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 128,580 KB
最終ジャッジ日時 2024-09-13 23:43:51
合計ジャッジ時間 20,428 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import *
inf = 1 << 61
def dijkstra(S,N,G):
  dist = [inf for i in range(N)]
  dist[S] = 0
  hq = [(0,S)]
  while len(hq):
    d,u = heappop(hq)
    if dist[u] < d:
      continue
    for v,c in G[u]:
      if dist[v] > dist[u] + c:
        dist[v] = dist[u] + c
        heappush(hq,(dist[v],v))
  return dist

N,M = map(int,input().split())
G = [[] for u in range(N)]
for _ in range(M):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  G[u].append((v,1))
  G[v].append((u,1))

dist = dijkstra(0,N,G)
C = [0 for u in range(N)]
for u in range(N):
  if dist[u] == inf:
    continue
  C[dist[u]] += 1
o,e = 0,0
e = 1
for i in range(1,N):
  if i % 2:
    o += C[i]
    print(o)
    if o == 0:
      e = 0
  else:
    e += C[i]
    print(e)
    if e == 0:
      o = 0
if N % 2:
  print(o)
else:
  print(e)
0