結果

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

ソースコード

diff # 

import sys
from collections import deque, defaultdict

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)
    components = []
    component_id = [0] * (N + 1)
    parent = [0] * (N + 1)
    up = [[-1] * 20 for _ in range(N + 1)]
    depth = [0] * (N + 1)

    for u in range(1, N + 1):
        if not visited[u]:
            q = deque()
            q.append(u)
            visited[u] = True
            component = []
            component.append(u)
            parent[u] = -1
            while q:
                v = q.popleft()
                for neighbor in edges[v]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        q.append(neighbor)
                        parent[neighbor] = v
                        component.append(neighbor)
            components.append(component)
            for node in component:
                component_id[node] = len(components) - 1
            
            root = component[0]
            depth[root] = 0
            for node in component:
                up[node][0] = parent[node] if parent[node] != -1 else -1
            
            for k in range(1, 20):
                for node in component:
                    if up[node][k-1] != -1:
                        up[node][k] = up[up[node][k-1]][k-1]
                    else:
                        up[node][k] = -1
            
            q = deque()
            q.append(root)
            depth[root] = 0
            while q:
                v = q.popleft()
                for neighbor in edges[v]:
                    if parent[neighbor] == v and neighbor != parent[v]:
                        depth[neighbor] = depth[v] + 1
                        q.append(neighbor)
    
    sum_same = 0

    P = defaultdict(list)
    for _ in range(Q):
        a, b = map(int, sys.stdin.readline().split())
        if component_id[a] == component_id[b]:
            c = component_id[a]
            u, v = a, b
            if depth[u] < depth[v]:
                u, v = v, u
            for k in range(19, -1, -1):
                if depth[u] - (1 << k) >= depth[v]:
                    u = up[u][k]
            if u == v:
                lca_node = u
            else:
                for k in range(19, -1, -1):
                    if up[u][k] != -1 and up[u][k] != up[v][k]:
                        u = up[u][k]
                        v = up[v][k]
                lca_node = parent[u]
            distance = depth[a] + depth[b] - 2 * depth[lca_node]
            sum_same += distance
        else:
            P[component_id[a]].append(a)
            P[component_id[b]].append(b)
    
    sum_diff = 0

    for c in range(len(components)):
        component = components[c]
        if c not in P:
            continue
        P_C = P[c]
        if not P_C:
            continue
        
        children = defaultdict(list)
        for node in component:
            if parent[node] != -1:
                children[parent[node]].append(node)
        root = component[0]
        
        weight = defaultdict(int)
        for u in P_C:
            weight[u] = 1
        
        cnt = defaultdict(int)
        res = defaultdict(int)
        
        stack = [(root, False)]
        while stack:
            u, done = stack.pop()
            if done:
                cnt[u] = 0
                res[u] = 0
                for v in children[u]:
                    cnt[u] += cnt[v]
                    res[u] += res[v] + cnt[v]
                if weight[u]:
                    cnt[u] += 1
            else:
                stack.append((u, True))
                for v in children[u]:
                    stack.append((v, False))
        
        total = len(P_C)
        stack = [root]
        while stack:
            u = stack.pop()
            for v in children[u]:
                res[v] = res[u] - cnt[v] + (total - cnt[v])
                stack.append(v)
        
        min_res = min(res.values())
        sum_diff += min_res
    
    print(sum_same + sum_diff)

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