結果

問題 No.2403 "Eight" Bridges of Königsberg
コンテスト
ユーザー detteiuu
提出日時 2025-03-03 00:21:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,025 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 109,456 KB
最終ジャッジ日時 2025-03-03 00:21:18
合計ジャッジ時間 6,266 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 10**18

cnt = [[0]*2 for _ in range(N)]
for u, v in edge:
    u, v = u-1, v-1
    cnt[u][0] += 1
    cnt[v][1] += 1

dp = [[INF]*(1<<2) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for bit in range(1<<2):
        if dp[i][bit] == INF:
            continue
        dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]+abs(cnt[i][0]-cnt[i][1]))
        if not 1<<0 & bit:
            if cnt[i][0]-1 >= cnt[i][1]:
                dp[i+1][bit|1<<0] = min(dp[i+1][bit|1<<0], dp[i][bit]+cnt[i][0]-1-cnt[i][1])
            else:
                dp[i+1][bit|1<<0] = min(dp[i+1][bit|1<<0], dp[i][bit]+cnt[i][1]+1-cnt[i][0])
        if not 1<<1 & bit:
            if cnt[i][1]-1 >= cnt[i][0]:
                dp[i+1][bit|1<<1] = min(dp[i+1][bit|1<<1], dp[i][bit]+cnt[i][1]-1-cnt[i][0])
            else:
                dp[i+1][bit|1<<0] = min(dp[i+1][bit|1<<0], dp[i][bit]+cnt[i][0]+1-cnt[i][1])

print(min(dp[-1][0], dp[-1][3])//2)
0