結果

問題 No.2888 Mamehinata
ユーザー 学ぶマン
提出日時 2025-02-05 21:48:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 601 ms / 2,000 ms
コード長 1,786 bytes
コンパイル時間 586 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 132,256 KB
最終ジャッジ日時 2025-02-05 21:49:15
合計ジャッジ時間 18,830 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, math; sys.setrecursionlimit(10**8); sys.set_int_max_str_digits(0)
inf = 1<<60; MOD = 998244353
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import product, combinations, permutations, groupby, accumulate
from heapq import heapify, heappop, heappush
def I():   return sys.stdin.readline().rstrip()
def II():  return int(sys.stdin.readline().rstrip())
def IS():  return sys.stdin.readline().rstrip().split()
def MII(): return map(int, sys.stdin.readline().rstrip().split())
def LI():  return list(sys.stdin.readline().rstrip())
def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split()))
def LII(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LSI(): return list(map(str, sys.stdin.readline().rstrip().split()))
def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
def kiriage(a, b): return (a+b-1)//b

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

if len(G[0]) == 0:
    for i in range(N):
        print(0)
    exit()

# BFS
dist = [-1] * N
dist[0] = 0
que = deque([0])
while que:
    pos = que.popleft()
    for nex in G[pos]:
        if dist[nex] == -1:
            dist[nex] = dist[pos] + 1
            que.append(nex)

# dist -> cnt
odd = [0] * (N + 1)
even = [0] * (N + 1)
for i in range(N):
    if dist[i] == -1:
        continue
    if dist[i]%2 == 0:
        even[dist[i]] += 1
    else:
        odd[dist[i]] += 1

rui_odd = list(accumulate(odd))
rui_even = list(accumulate(even))

for i in range(1, N + 1):
    if i&1:
        ans = rui_odd[i]
    else:
        ans = rui_even[i]
    print(ans)
0