結果

問題 No.1479 Matrix Eraser
ユーザー titiatitia
提出日時 2024-05-07 04:37:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 650 ms / 3,000 ms
コード長 2,759 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 130,584 KB
最終ジャッジ日時 2024-05-07 04:37:30
合計ジャッジ時間 15,231 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
75,648 KB
testcase_01 AC 55 ms
76,544 KB
testcase_02 AC 64 ms
76,672 KB
testcase_03 AC 56 ms
76,672 KB
testcase_04 AC 56 ms
76,416 KB
testcase_05 AC 56 ms
76,416 KB
testcase_06 AC 55 ms
76,544 KB
testcase_07 AC 201 ms
100,076 KB
testcase_08 AC 226 ms
100,208 KB
testcase_09 AC 271 ms
106,548 KB
testcase_10 AC 413 ms
112,108 KB
testcase_11 AC 301 ms
107,876 KB
testcase_12 AC 207 ms
99,992 KB
testcase_13 AC 229 ms
100,808 KB
testcase_14 AC 218 ms
100,276 KB
testcase_15 AC 95 ms
96,000 KB
testcase_16 AC 224 ms
100,792 KB
testcase_17 AC 487 ms
114,412 KB
testcase_18 AC 481 ms
114,628 KB
testcase_19 AC 458 ms
115,244 KB
testcase_20 AC 469 ms
114,888 KB
testcase_21 AC 497 ms
114,836 KB
testcase_22 AC 471 ms
114,792 KB
testcase_23 AC 482 ms
114,544 KB
testcase_24 AC 458 ms
114,512 KB
testcase_25 AC 468 ms
114,432 KB
testcase_26 AC 492 ms
115,028 KB
testcase_27 AC 609 ms
113,116 KB
testcase_28 AC 611 ms
113,428 KB
testcase_29 AC 633 ms
112,900 KB
testcase_30 AC 650 ms
113,960 KB
testcase_31 AC 627 ms
114,560 KB
testcase_32 AC 302 ms
130,304 KB
testcase_33 AC 283 ms
130,432 KB
testcase_34 AC 278 ms
130,304 KB
testcase_35 AC 277 ms
130,584 KB
testcase_36 AC 310 ms
130,304 KB
testcase_37 AC 93 ms
99,456 KB
testcase_38 AC 479 ms
117,632 KB
testcase_39 AC 127 ms
99,712 KB
testcase_40 AC 54 ms
75,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from operator import itemgetter

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]

LIST=[[] for i in range(500050)]

for i in range(H):
    for j in range(W):
        LIST[A[i][j]].append(i*W+j)

LANS=0   
# dinic法

from collections import defaultdict,deque

for tt in range(1,500020):
    LL=LIST[tt]

    if LL==[]:
        continue
    if len(LL)==1:
        LANS+=1
        continue

    LH=[]
    LW=[]

    for ll in LL:
        LH.append(ll//W)
        LW.append(ll%W)

    LH=sorted(set(LH))
    LW=sorted(set(LW))

    DH={LH[i]:i for i in range(len(LH))}
    DW={LW[i]:i for i in range(len(LW))}
    
    V=len(LH)+len(LW)+2

    start=V-2
    goal=V-1

    EDGE=[defaultdict(int) for i in range(V)]

    for i in range(len(LH)):
        EDGE[start][i]=1

    for i in range(len(LW)):
        EDGE[i+len(LH)][goal]=1

    for ll in LL:
        h=ll//W
        w=ll%W
        EDGE[DH[h]][DW[w]+len(LH)]=1000000

    

    ANS=0
    while True:
        # まずBFSする

        DIS=[-1]*V
        Q=deque([start])
        DIS[start]=0
        EDGE2=[[] for i in range(V)]

        while Q:
            x=Q.popleft()
            for to in EDGE[x]:
                if EDGE[x][to]==0:
                    continue
                
                if DIS[to]==-1:
                    DIS[to]=DIS[x]+1
                    Q.append(to)
                    EDGE2[x].append(to)
                    
                elif DIS[to]==DIS[x]+1:
                    EDGE2[x].append(to)

        if DIS[goal]==-1:
            break

        # BFSしたときのEDGEを使ってDFSする

        MINCOST=[float("inf")]*V
        NOW=start
        ROUTE=[-1]*V
        
        while NOW!=-1: # DFS

            cost=MINCOST[NOW]
            
            if NOW==goal:
                ANS+=cost
                i=goal
                
                while i!=start: # goalからたどり,Routeを使ってEDGEの更新
                    j=ROUTE[i]
                    if EDGE[j][i]==cost:
                        NOW=j
                        EDGE2[j].pop()
                    
                    EDGE[j][i]-=cost # 使ったルートをいけなく更新
                    MINCOST[j]-=cost                
                    EDGE[i][j]+=cost # 逆向きに進めるようにする.
                    i=j
                continue

            if EDGE2[NOW]:
                to=EDGE2[NOW][-1]
                ROUTE[to]=NOW
                MINCOST[to]=min(cost,EDGE[NOW][to])
                NOW=to

            else:
                if NOW==start:
                    break
                EDGE2[ROUTE[NOW]].pop()
                NOW=ROUTE[NOW]
    LANS+=ANS
         

print(LANS)
0