結果

問題 No.812 Change of Class
ユーザー persimmon-persimmon
提出日時 2021-06-17 13:49:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,158 ms / 4,000 ms
コード長 925 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 196,132 KB
最終ジャッジ日時 2025-01-02 18:20:59
合計ジャッジ時間 28,934 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(m)]
q=int(input())
a=[int(input()) for _ in range(q)]
g=[[] for _ in range(n)]
for p,q in pq:
  p,q=p-1,q-1
  g[p].append(q)
  g[q].append(p)
from collections import deque
for v in a:
  v-=1
  todo=deque([v])
  d={}
  d[v]=0
  while todo:
    v=todo.popleft()
    for nv in g[v]:
      if nv not in d:
        d[nv]=d[v]+1
        todo.append(nv)
  x=d[v]
  for i in range(31):
    if x<=pow(2,i):
      print(len(d)-1,i)
      break

"""
スターグラフなら1日目で達成
長さLのパスグラフならlog(L)??
周長Lの閉路グラフなら
それぞれの連結成分で一番最後に友達になるペアを見つける
log(最長パス)かな？
1日目:距離2の頂点間に辺
2日目:距離3,4の頂点間に辺
3日目:距離5~8の頂点間に辺
4日目:距離9~16の頂点間に辺
5日目:距離17~32の頂点間に辺
"""
0