結果

問題 No.1194 Replace
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:45:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 794 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 100,392 KB
最終ジャッジ日時 2025-04-15 21:46:48
合計ジャッジ時間 6,064 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())

replace_map = {}

for _ in range(M):
    B, C = map(int, input().split())
    if C > B:
        if B in replace_map:
            if C > replace_map[B]:
                replace_map[B] = C
        else:
            replace_map[B] = C

cache = {}
sum_gain = 0

for B in replace_map:
    current = B
    path = []
    while True:
        if current in cache:
            value = cache[current]
            break
        if current not in replace_map:
            value = current
            break
        path.append(current)
        current = replace_map[current]
    # Update cache for all nodes in the path
    for node in path:
        cache[node] = value
    sum_gain += (value - B)

initial_sum = N * (N + 1) // 2
total = initial_sum + sum_gain

print(total)
0