結果

問題 No.1194 Replace
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:11:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 768 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 81,992 KB
実行使用メモリ 96,232 KB
最終ジャッジ日時 2025-06-12 18:13:11
合計ジャッジ時間 7,709 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

max_map = {}

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

cache = {}

def get_final(i):
    if i not in max_map:
        return i
    if i in cache:
        return cache[i]
    path = []
    current = i
    while current in max_map:
        if current in cache:
            final = cache[current]
            break
        path.append(current)
        current = max_map[current]
    else:
        final = current
    # Update cache for all nodes in the path
    for node in path:
        cache[node] = final
    return final

total = n * (n + 1) // 2

for b in max_map:
    final = get_final(b)
    total += (final - b)

print(total)
0