結果

問題 No.3024 全単射的
ユーザー 👑 p-adic
提出日時 2024-05-27 09:56:42
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,482 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 167,564 KB
最終ジャッジ日時 2024-12-20 20:30:49
合計ジャッジ時間 36,669 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import queue
R=range
def HopcroftKarp(S,T,edge):
    unchosen_source=set(R(S))
    prev=[-1]*T
    chosen_source=[0]*S
    chosen_target=[0]*T
    chosen_edge=[{}for s in R(S)]
    depth=[0]*(1+S+T)
    depth_min=-1
    root=[0]*(S+T)
    new_chosen_target=[0]
    while len(new_chosen_target):
        new_chosen_target=[]
        V=queue.Queue()
        D=[-1]*(1+S+T)
        last=D[:]
        D[0]=found=0
        for s in unchosen_source:V.put(1+s);D[1+s],last[1+s]=1,0
        while V.qsize():
            v=V.get()
            w=last[v]
            E=[]
            if v>S:
                s=prev[v-1-S]
                if 1+s:E=[1+s]
            else:E+=[1+S+t for t in edge[v-1]]
            for u in E:
                if D[u]<0:V.put(u);D[u],last[u]=D[v]+1,v;
            if found and D[v]>depth_min:break
            root[v-1]=root[w-1]if w else v-1
            if D[v]&1<1:
                t=v-1-S
                if chosen_target[t]<1:
                    s=root[v-1]
                    if chosen_source[s]<1:
                        chosen_source[s]=chosen_target[t]=1;new_chosen_target+=[v]
                        if found<1:found,depth_min=1,D[v]
        for nct in new_chosen_target:
            p,i=[last[nct],nct],0
            while p[0]:
                s,t=p[i]-1,p[i^1]-1-S
                if t in chosen_edge[s]:chosen_edge[s][t]^=1
                else:chosen_edge[s][t]=1
                if chosen_edge[s][t]:prev[t]=s
                p,i=[last[p[0]],p[0]],i^1
            unchosen_source.remove(p[1]-1)
    return[[prev[t],t]for t in R(T)if 1+prev[t]]
def CoordinateCompressA(A):
    Z={}
    for X in A:
        for i in R(len(X)):
            if X[i] in Z:X[i]=Z[X[i]]
            else:Z[X[i]]=X[i]=len(Z)
    return len(Z)
J=lambda:map(int,input().split())
N,M=J()
edge=[list(J())for i in R(N)]
M=CoordinateCompressA(edge)
print(len(HopcroftKarp(N,M,edge)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0