結果

問題 No.922 東北きりきざむたん
ユーザー lam6er
提出日時 2025-03-20 20:57:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,214 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 190,244 KB
最終ジャッジ日時 2025-03-20 20:58:19
合計ジャッジ時間 11,694 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    Q = int(input[idx]); idx +=1

    # Read edges and build adjacency list
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(input[idx]); idx +=1
        v = int(input[idx]); idx +=1
        adj[u].append(v)
        adj[v].append(u)

    # Variables for component processing
    visited = [False] * (N+1)
    component_id = [0] * (N+1)
    components = []
    parent = [0] * (N+1)
    depth = [0] * (N+1)
    children = [[] for _ in range(N+1)]
    current_cid = 0
    max_level = 20
    up = [[0]*max_level for _ in range(N+1)]

    # BFS to find components and compute parent, depth, children
    for u in range(1, N+1):
        if not visited[u]:
            q = deque()
            q.append(u)
            visited[u] = True
            component = []
            parent[u] = 0
            depth[u] = 0
            component.append(u)
            while q:
                v = q.popleft()
                for neighbor in adj[v]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        parent[neighbor] = v
                        depth[neighbor] = depth[v] + 1
                        children[v].append(neighbor)
                        component.append(neighbor)
                        q.append(neighbor)
            # Build binary lifting table for this component
            for node in component:
                up[node][0] = parent[node]
                for k in range(1, max_level):
                    if up[node][k-1] == 0:
                        up[node][k] = 0
                    else:
                        up[node][k] = up[up[node][k-1]][k-1]
            components.append(component)
            for node in component:
                component_id[node] = current_cid
            current_cid += 1

    # Process queries
    same_sum = 0
    cross_S = [set() for _ in range(current_cid + 2)]

    for _ in range(Q):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        if a == b:
            continue
        cid_a = component_id[a]
        cid_b = component_id[b]
        if cid_a == cid_b:
            # Compute distance using LCA
            u, v = a, b
            if depth[u] < depth[v]:
                u, v = v, u
            # Lift u to depth v
            for k in range(max_level-1, -1, -1):
                if depth[u] - (1 << k) >= depth[v]:
                    u = up[u][k]
            if u == v:
                lca_node = u
            else:
                for k in range(max_level-1, -1, -1):
                    if up[u][k] != up[v][k]:
                        u = up[u][k]
                        v = up[v][k]
                lca_node = up[u][0]
            dist = depth[a] + depth[b] - 2 * depth[lca_node]
            same_sum += dist
        else:
            cross_S[cid_a].add(a)
            cross_S[cid_b].add(b)

    # Compute minimal sum for each component with non-empty cross_S
    total_cross_sum = 0

    for cid in range(current_cid):
        S = cross_S[cid]
        if not S:
            continue
        component_nodes = components[cid]
        if len(component_nodes) == 1:
            # Only one node, sum is 0
            total_cross_sum += 0
            continue

        # Find the root (it's component_nodes[0] as per BFS)
        root = component_nodes[0]

        # Prepare post-order traversal
        post_order = []
        visited_po = {node: False for node in component_nodes}
        stack = [(root, False)]
        while stack:
            node, done = stack.pop()
            if done:
                post_order.append(node)
                continue
            if visited_po[node]:
                continue
            visited_po[node] = True
            stack.append((node, True))
            for child in reversed(children[node]):
                stack.append((child, False))

        # Initialize count and sum_dist_subtree
        count = {node:0 for node in component_nodes}
        sum_dist_subtree = {node:0 for node in component_nodes}

        for node in post_order:
            if node in S:
                count[node] = 1
            else:
                count[node] = 0
            sum_dist_subtree[node] = 0
            for child in children[node]:
                count[node] += count[child]
                sum_dist_subtree[node] += sum_dist_subtree[child] + count[child]

        # Pre-order traversal to compute sum_dist_total
        total_S = len(S)
        sum_dist_total = {node:0 for node in component_nodes}
        sum_dist_total[root] = sum_dist_subtree[root]
        q = deque([root])
        while q:
            u = q.popleft()
            for v in children[u]:
                sum_dist_total[v] = sum_dist_total[u] - count[v] + (total_S - count[v])
                q.append(v)

        # Find minimal sum
        min_sum = min(sum_dist_total[node] for node in component_nodes)
        total_cross_sum += min_sum

    print(same_sum + total_cross_sum)

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