結果

問題 No.1194 Replace
ユーザー gew1fw
提出日時 2025-06-12 12:58:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 888 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 114,844 KB
最終ジャッジ日時 2025-06-12 13:05:19
合計ジャッジ時間 8,059 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())

max_replace = {}

for _ in range(m):
    b, c = map(int, input().split())
    if c > b:
        if b in max_replace:
            if c > max_replace[b]:
                max_replace[b] = c
        else:
            max_replace[b] = c

visited = set()
final_values = {}
total_delta = 0

for b in max_replace.keys():
    if b not in visited:
        path = []
        current = b
        while current in max_replace and current not in visited:
            visited.add(current)
            path.append(current)
            current = max_replace[current]
        # Determine final value
        final = final_values.get(current, current)
        # Update final_values for all nodes in path
        for node in path:
            final_values[node] = final
            total_delta += final - node

initial_sum = n * (n + 1) // 2
print(initial_sum + total_delta)
0