結果

問題 No.1194 Replace
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:11:36
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 992 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 219,712 KB
最終ジャッジ日時 2025-04-15 22:13:29
合計ジャッジ時間 12,158 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 5 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

def main():
    N, M = map(int, stdin.readline().split())
    edges = defaultdict(list)
    S = set()
    for _ in range(M):
        B, C = map(int, stdin.readline().split())
        S.add(B)
        S.add(C)
        edges[B].append(C)
    
    max_reachable = dict()

    def compute(x):
        if x not in S:
            return x
        if x in max_reachable:
            return max_reachable[x]
        # Temporarily set to x to prevent infinite recursion
        max_reachable[x] = x
        current_max = x
        for c in edges[x]:
            candidate = compute(c)
            if candidate > current_max:
                current_max = candidate
        max_reachable[x] = current_max
        return current_max
    
    sum_diff = 0
    for x in S:
        compute(x)
        sum_diff += (max_reachable[x] - x)
    
    total = sum_diff + N * (N + 1) // 2
    print(total)

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