結果

問題 No.922 東北きりきざむたん
ユーザー gew1fw
提出日時 2025-06-12 20:37:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,904 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 261,268 KB
最終ジャッジ日時 2025-06-12 20:37:38
合計ジャッジ時間 7,156 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 WA * 2 TLE * 2 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M, Q = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
        edges[v].append(u)
    
    visited = [False] * (N + 1)
    component = [0] * (N + 1)
    current_component = 0
    component_info = []
    
    for u in range(1, N + 1):
        if not visited[u]:
            current_component += 1
            q = deque()
            q.append(u)
            visited[u] = True
            comp_nodes = []
            while q:
                node = q.popleft()
                comp_nodes.append(node)
                for v in edges[node]:
                    if not visited[v]:
                        visited[v] = True
                        q.append(v)
            for node in comp_nodes:
                component[node] = current_component
            component_info.append(comp_nodes)
    
    in_time = [0] * (N + 1)
    out_time = [0] * (N + 1)
    depth = [0] * (N + 1)
    parent = [0] * (N + 1)
    
    time_counter = 0
    for comp in component_info:
        root = comp[0]
        stack = [(root, False)]
        parent[root] = 0
        while stack:
            node, processed = stack.pop()
            if processed:
                out_time[node] = time_counter
                time_counter += 1
            else:
                in_time[node] = time_counter
                time_counter += 1
                stack.append((node, True))
                children = []
                for v in edges[node]:
                    if component[v] == component[node] and v != parent[node]:
                        children.append(v)
                children.sort(reverse=True)
                for v in children:
                    if parent[v] == 0:
                        parent[v] = node
                        depth[v] = depth[node] + 1
                        stack.append((v, False))
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        while depth[u] > depth[v]:
            u = parent[u]
        if u == v:
            return u
        while parent[u] != parent[v]:
            u = parent[u]
            v = parent[v]
        return parent[u]
    
    distance_same = 0
    S = dict()
    for _ in range(Q):
        a, b = map(int, sys.stdin.readline().split())
        if component[a] == component[b]:
            ancestor = lca(a, b)
            dist = depth[a] + depth[b] - 2 * depth[ancestor]
            distance_same += dist
        else:
            if component[a] not in S:
                S[component[a]] = []
            S[component[a]].append(a)
            if component[b] not in S:
                S[component[b]] = []
            S[component[b]].append(b)
    
    total = distance_same
    
    for comp in component_info:
        comp_id = component[comp[0]]
        if comp_id not in S:
            continue
        S_C = S[comp_id]
        if not S_C:
            continue
        
        root = comp[0]
        current_u = root
        sum_dist = [0] * (N + 1)
        for s in S_C:
            sum_dist[s] += 1
        
        stack = [current_u]
        best_sum = float('inf')
        best_u = current_u
        
        for u in S_C:
            temp_sum = 0
            for v in S_C:
                ancestor = lca(u, v)
                temp_sum += depth[u] + depth[v] - 2 * depth[ancestor]
            if temp_sum < best_sum:
                best_sum = temp_sum
                best_u = u
        
        current_u = best_u
        
        current_sum = 0
        for s in S_C:
            ancestor = lca(current_u, s)
            current_sum += depth[current_u] + depth[s] - 2 * depth[ancestor]
        
        total += current_sum
    
    print(total)

if __name__ == "__main__":
    main()
0