結果
問題 |
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 sys from math import log2 def 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 ** 19 MOD = 10 ** 9 + 7 EPS = 10 ** -10 def bfs(nodes, src): """ BFS(一般グラフ、重みなし) """ from collections import deque N = len(nodes) que = deque([src]) dist = [INF] * N dist[src] = 0 cnt = 0 while que: u = que.popleft() for v in nodes[u]: if dist[v] != INF: continue dist[v] = dist[u] + 1 que.append(v) cnt += 1 mx = 0 for i in range(N): if dist[i] != INF and dist[i] >= 2: mx = max(mx, ceil(log2(dist[i]))) return cnt, mx N, M = MAP() nodes = [[] for i in range(N)] for i in range(M): a, b = MAP() a -= 1; b -= 1 nodes[a].append(b) nodes[b].append(a) Q = INT() for _ in range(Q): x = INT() x -= 1 cnt, mx = bfs(nodes, x) print(cnt, mx)