結果

問題 No.1194 Replace
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:15:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,677 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 466,736 KB
最終ジャッジ日時 2025-06-12 18:16:18
合計ジャッジ時間 36,023 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 20 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    replace_map = {}
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        if B not in replace_map or C > replace_map[B]:
            replace_map[B] = C

    # Build the graph and reverse graph for Kosaraju's algorithm
    graph = defaultdict(list)
    reverse_graph = defaultdict(list)
    for B in replace_map:
        C = replace_map[B]
        graph[B].append(C)
        reverse_graph[C].append(B)

    # First pass to get finishing order using DFS
    visited = set()
    order = []
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if node in visited:
                continue
            visited.add(node)
            stack.append((node, True))
            for v in graph.get(node, []):
                if v not in visited:
                    stack.append((v, False))
    for u in replace_map:
        if u not in visited:
            dfs(u)

    # Second pass to find SCCs using reverse graph
    visited = set()
    sccs = []
    def reverse_dfs(u, scc):
        stack = [u]
        visited.add(u)
        scc.add(u)
        while stack:
            node = stack.pop()
            for v in reverse_graph.get(node, []):
                if v not in visited:
                    visited.add(v)
                    stack.append(v)
                    scc.add(v)
    for u in reversed(order):
        if u not in visited:
            scc = set()
            reverse_dfs(u, scc)
            sccs.append(scc)

    # Compute maximum value for each SCC
    scc_max = {}
    for scc in sccs:
        max_val = max(scc)
        for node in scc:
            scc_max[node] = max_val

    # Build DAG between SCCs' max values
    dag = defaultdict(set)
    for B in replace_map:
        C = replace_map[B]
        B_scc_max = scc_max.get(B, B)
        C_scc_max = scc_max.get(C, C)
        if B_scc_max != C_scc_max:
            dag[B_scc_max].add(C_scc_max)

    # Topological sort on DAG
    in_degree = defaultdict(int)
    for u in dag:
        for v in dag[u]:
            in_degree[v] += 1
    queue = deque()
    for u in dag:
        if in_degree[u] == 0:
            queue.append(u)
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in dag[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    topo_order.reverse()

    # Compute max_reachable for each SCC in topological order
    scc_max_reachable = {}
    for u in topo_order:
        max_val = u
        for v in dag[u]:
            max_val = max(max_val, scc_max_reachable.get(v, v))
        scc_max_reachable[u] = max_val

    # Handle SCCs not in DAG (isolated nodes)
    for scc in sccs:
        max_val = max(scc)
        if max_val not in scc_max_reachable:
            scc_max_reachable[max_val] = max_val

    # Calculate max_reachable for each node in replace_map
    node_max_reachable = {}
    for B in replace_map:
        scc_max_val = scc_max.get(B, B)
        node_max_reachable[B] = scc_max_reachable.get(scc_max_val, scc_max_val)

    # Compute the total sum
    initial_sum = N * (N + 1) // 2
    additional = 0
    for B in replace_map:
        current_max = node_max_reachable.get(B, B)
        if current_max > B:
            additional += (current_max - B)
    total = initial_sum + additional
    print(total)

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