結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:31:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,044 ms / 4,000 ms |
コード長 | 2,191 bytes |
コンパイル時間 | 459 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 112,884 KB |
最終ジャッジ日時 | 2025-03-31 17:32:59 |
合計ジャッジ時間 | 23,028 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
import sys from math import log2, ceil from collections import deque def main(): sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 adj = [[] for _ in range(N + 1)] # Nodes are 1-based for _ in range(M): p = int(input[ptr]) ptr += 1 q = int(input[ptr]) ptr += 1 adj[p].append(q) adj[q].append(p) # Precompute components and their sizes component = [0] * (N + 1) component_size = {} visited = [False] * (N + 1) current_comp = 0 for node in range(1, N + 1): if not visited[node]: current_comp += 1 q = deque() q.append(node) visited[node] = True cnt = 0 while q: u = q.popleft() component[u] = current_comp cnt += 1 for v in adj[u]: if not visited[v]: visited[v] = True q.append(v) component_size[current_comp] = cnt Q = int(input[ptr]) ptr += 1 queries = [] for _ in range(Q): a = int(input[ptr]) ptr += 1 queries.append(a) for a in queries: comp_id = component[a] size = component_size[comp_id] if size == 1: print(0, 0) continue # BFS to find max distance from a in its component max_dist = 0 dist = [-1] * (N + 1) q = deque() dist[a] = 0 q.append(a) while q: u = q.popleft() for v in adj[u]: if dist[v] == -1: dist[v] = dist[u] + 1 max_dist = max(max_dist, dist[v]) q.append(v) # Compute day: smallest k where 2^k >= max_dist if max_dist == 0: day = 0 else: day = 0 current = 1 while current < max_dist: current <<= 1 day += 1 print(size - 1, day) if __name__ == '__main__': main()