結果

問題 No.812 Change of Class
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0