結果

問題 No.1194 Replace
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:21:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,421 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 121,712 KB
最終ジャッジ日時 2025-03-31 17:22:42
合計ジャッジ時間 8,264 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

def main():
    N, M = map(int, sys.stdin.readline().split())
    max_c = {}

    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        if C > B:
            if B not in max_c or C > max_c[B]:
                max_c[B] = C

    # Build reverse graph
    reverse_graph = defaultdict(list)
    for B in max_c:
        C = max_c[B]
        reverse_graph[C].append(B)

    visited = set()
    total_gain = 0

    # Process each termination node (w not in max_c) in reverse_graph
    for w in list(reverse_graph.keys()):
        if w not in max_c and w not in visited:
            queue = deque([w])
            count = 0
            sum_u = 0
            local_visited = set()

            while queue:
                node = queue.popleft()
                if node in visited or node in local_visited:
                    continue
                local_visited.add(node)
                count += 1
                sum_u += node
                # Append all neighbors (B's that point to current node)
                for neighbor in reverse_graph.get(node, []):
                    queue.append(neighbor)

            gain = count * w - sum_u
            total_gain += gain
            visited.update(local_visited)

    initial_sum = N * (N + 1) // 2
    total = initial_sum + total_gain
    print(total)

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