結果

問題 No.1194 Replace
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:57:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 898 bytes
コンパイル時間 481 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 97,000 KB
最終ジャッジ日時 2025-06-12 13:03:57
合計ジャッジ時間 8,260 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

cache = {}

def get_max(x):
    if x not in max_replace:
        return x
    if x in cache:
        return cache[x]
    path = []
    current = x
    while current in max_replace and current not in cache:
        path.append(current)
        current = max_replace[current]
    if current in cache:
        res = cache[current]
    else:
        res = current
    for node in path:
        cache[node] = res
    cache[x] = res
    return res

total_increment = 0
for B in max_replace:
    max_val = get_max(B)
    total_increment += (max_val - B)

initial_sum = N * (N + 1) // 2
result = initial_sum + total_increment
print(result)
0