結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2020-08-18 18:57:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,412 ms / 4,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 83,040 KB |
実行使用メモリ | 126,604 KB |
最終ジャッジ日時 | 2024-10-12 03:07:37 |
合計ジャッジ時間 | 31,882 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
import sysfrom math import log2def input(): return sys.stdin.readline().strip()def list2d(a, b, c): return [[c] * b for i in range(a)]def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]def ceil(x, y=1): return int(-(-x // y))def INT(): return int(input())def MAP(): return map(int, input().split())def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]def Yes(): print('Yes')def No(): print('No')def YES(): print('YES')def NO(): print('NO')sys.setrecursionlimit(10 ** 9)INF = 10 ** 19MOD = 10 ** 9 + 7EPS = 10 ** -10def bfs(nodes, src):""" BFS(一般グラフ、重みなし) """from collections import dequeN = len(nodes)que = deque([src])dist = [INF] * Ndist[src] = 0cnt = 0while que:u = que.popleft()for v in nodes[u]:if dist[v] != INF:continuedist[v] = dist[u] + 1que.append(v)cnt += 1mx = 0for i in range(N):if dist[i] != INF and dist[i] >= 2:mx = max(mx, ceil(log2(dist[i])))return cnt, mxN, M = MAP()nodes = [[] for i in range(N)]for i in range(M):a, b = MAP()a -= 1; b -= 1nodes[a].append(b)nodes[b].append(a)Q = INT()for _ in range(Q):x = INT()x -= 1cnt, mx = bfs(nodes, x)print(cnt, mx)