結果

問題 No.2888 Mamehinata
ユーザー PNJPNJ
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,476 KB
testcase_01 AC 39 ms
53,688 KB
testcase_02 AC 40 ms
53,080 KB
testcase_03 AC 38 ms
53,388 KB
testcase_04 AC 38 ms
53,172 KB
testcase_05 AC 41 ms
54,380 KB
testcase_06 AC 42 ms
54,040 KB
testcase_07 AC 40 ms
54,344 KB
testcase_08 AC 40 ms
53,352 KB
testcase_09 AC 39 ms
53,604 KB
testcase_10 AC 38 ms
53,204 KB
testcase_11 AC 40 ms
53,324 KB
testcase_12 AC 42 ms
54,624 KB
testcase_13 AC 221 ms
85,636 KB
testcase_14 AC 143 ms
85,784 KB
testcase_15 AC 388 ms
100,460 KB
testcase_16 AC 610 ms
107,444 KB
testcase_17 AC 133 ms
87,784 KB
testcase_18 AC 345 ms
91,680 KB
testcase_19 AC 686 ms
110,232 KB
testcase_20 AC 591 ms
105,056 KB
testcase_21 AC 602 ms
104,512 KB
testcase_22 AC 188 ms
93,568 KB
testcase_23 AC 246 ms
99,592 KB
testcase_24 AC 544 ms
106,956 KB
testcase_25 AC 309 ms
103,980 KB
testcase_26 AC 412 ms
103,144 KB
testcase_27 AC 188 ms
94,940 KB
testcase_28 AC 217 ms
82,236 KB
testcase_29 AC 329 ms
90,052 KB
testcase_30 AC 630 ms
107,896 KB
testcase_31 AC 548 ms
103,184 KB
testcase_32 AC 415 ms
95,352 KB
testcase_33 AC 512 ms
100,964 KB
testcase_34 AC 454 ms
98,060 KB
testcase_35 AC 403 ms
94,520 KB
testcase_36 AC 691 ms
111,048 KB
testcase_37 AC 701 ms
112,076 KB
testcase_38 AC 221 ms
86,612 KB
testcase_39 AC 471 ms
104,180 KB
testcase_40 AC 562 ms
110,748 KB
testcase_41 AC 169 ms
82,828 KB
testcase_42 AC 492 ms
105,384 KB
testcase_43 AC 549 ms
116,252 KB
testcase_44 AC 607 ms
121,668 KB
testcase_45 AC 675 ms
128,580 KB
testcase_46 AC 175 ms
82,280 KB
testcase_47 AC 593 ms
120,992 KB
testcase_48 AC 518 ms
110,368 KB
testcase_49 AC 107 ms
79,416 KB
testcase_50 AC 201 ms
92,652 KB
testcase_51 AC 69 ms
73,816 KB
testcase_52 AC 65 ms
70,808 KB
testcase_53 AC 88 ms
76,876 KB
testcase_54 AC 37 ms
53,444 KB
権限があれば一括ダウンロードができます

ソースコード

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