結果
問題 |
No.812 Change of Class
|
ユーザー |
|
提出日時 | 2022-04-18 23:15:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,113 ms / 4,000 ms |
コード長 | 979 bytes |
コンパイル時間 | 547 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 151,680 KB |
最終ジャッジ日時 | 2024-12-30 07:21:55 |
合計ジャッジ時間 | 30,206 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
import collections N,M = map(int,input().split()) lsg = [[] for i in range(N)] for i in range(M): p,q = map(int,input().split()) p -= 1 q -= 1 lsg[p].append(q) lsg[q].append(p) Q = int(input()) ans = [] inf = float('INF') for i in range(Q): a = int(input())-1 used = [False]*(N) d = collections.deque([a]) cost = [inf]*(N) cost[a] = 0 while d: n = d.popleft() if used[n]: continue used[n] = True for j in lsg[n]: if used[j]: continue if cost[j] > cost[n]+1: cost[j] = cost[n]+1 d.append(j) cnt = 0 maxn = 0 for j in range(N): if cost[j] != inf: cnt += 1 maxn = max(maxn,cost[j]) if maxn == 0: ans.append((0,0)) elif maxn == 1: ans.append((cnt-1,0)) else: ans.append((cnt-1,len(bin(maxn-1))-2)) for i in range(Q): print(*ans[i],sep=' ')