結果

問題 No.812 Change of Class
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-17 13:49:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,054 ms / 4,000 ms
コード長 925 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 193,748 KB
最終ジャッジ日時 2024-06-10 20:47:15
合計ジャッジ時間 27,216 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 496 ms
168,620 KB
testcase_01 AC 156 ms
88,948 KB
testcase_02 AC 316 ms
126,484 KB
testcase_03 AC 581 ms
188,216 KB
testcase_04 AC 523 ms
178,664 KB
testcase_05 AC 1,054 ms
172,904 KB
testcase_06 AC 771 ms
156,480 KB
testcase_07 AC 44 ms
60,160 KB
testcase_08 AC 43 ms
59,264 KB
testcase_09 AC 893 ms
166,984 KB
testcase_10 AC 954 ms
166,700 KB
testcase_11 AC 93 ms
77,712 KB
testcase_12 AC 597 ms
143,480 KB
testcase_13 AC 39 ms
54,016 KB
testcase_14 AC 40 ms
54,016 KB
testcase_15 AC 694 ms
147,628 KB
testcase_16 AC 131 ms
78,880 KB
testcase_17 AC 590 ms
143,444 KB
testcase_18 AC 456 ms
129,924 KB
testcase_19 AC 523 ms
138,752 KB
testcase_20 AC 984 ms
168,172 KB
testcase_21 AC 429 ms
121,112 KB
testcase_22 AC 251 ms
100,540 KB
testcase_23 AC 122 ms
78,464 KB
testcase_24 AC 126 ms
78,756 KB
testcase_25 AC 217 ms
94,848 KB
testcase_26 AC 824 ms
161,772 KB
testcase_27 AC 694 ms
148,436 KB
testcase_28 AC 496 ms
138,432 KB
testcase_29 AC 186 ms
87,620 KB
testcase_30 AC 633 ms
146,256 KB
testcase_31 AC 557 ms
141,152 KB
testcase_32 AC 292 ms
105,600 KB
testcase_33 AC 691 ms
154,464 KB
testcase_34 AC 123 ms
78,632 KB
testcase_35 AC 203 ms
94,188 KB
testcase_36 AC 141 ms
79,104 KB
testcase_37 AC 385 ms
120,396 KB
testcase_38 AC 79 ms
78,800 KB
testcase_39 AC 388 ms
118,496 KB
testcase_40 AC 160 ms
83,968 KB
testcase_41 AC 73 ms
75,020 KB
testcase_42 AC 794 ms
162,328 KB
testcase_43 AC 164 ms
91,144 KB
testcase_44 AC 546 ms
142,404 KB
testcase_45 AC 144 ms
79,200 KB
testcase_46 AC 150 ms
88,704 KB
testcase_47 AC 516 ms
145,596 KB
testcase_48 AC 530 ms
136,936 KB
testcase_49 AC 229 ms
94,592 KB
testcase_50 AC 87 ms
76,656 KB
testcase_51 AC 211 ms
97,328 KB
testcase_52 AC 301 ms
115,792 KB
testcase_53 AC 177 ms
86,812 KB
testcase_54 AC 172 ms
84,092 KB
testcase_55 AC 451 ms
164,236 KB
testcase_56 AC 515 ms
179,716 KB
testcase_57 AC 511 ms
178,548 KB
testcase_58 AC 316 ms
128,684 KB
testcase_59 AC 612 ms
193,748 KB
testcase_60 AC 40 ms
53,888 KB
testcase_61 AC 39 ms
53,632 KB
testcase_62 AC 39 ms
54,016 KB
権限があれば一括ダウンロードができます

ソースコード

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