結果

問題 No.3034 コーエン-マコーレー抽象単体複体
ユーザー 👑 p-adic
提出日時 2025-01-24 20:37:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,460 ms / 2,000 ms
コード長 1,753 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 103,304 KB
最終ジャッジ日時 2025-02-06 22:27:26
合計ジャッジ時間 20,462 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

R=range
class UnionFindForest:
    def __init__(__self__,N):
        __self__.c=__self__.N=N
        __self__.P=list(R(N))
        __self__.H=[0]*N
    def RootOfNode(__self__,i):
        m=__self__.P[i]
        while i!=m:__self__.P[i]=__self__.P[m];i=__self__.P[i];m=__self__.P[i]
        return i
    def Graft(__self__,u,v):
        u,v=__self__.RootOfNode(u),__self__.RootOfNode(v)
        if __self__.H[v]<__self__.H[u]:u,v=v,u
        __self__.H[v]+=__self__.H[u]==__self__.H[v];__self__.P[u]=v;__self__.c-=u!=v
    def NodeSize(__self__):return __self__.N
    def RootSize(__self__):return __self__.c
J=lambda:map(int,input().split())
N,M=J()
appeared=[0]*N
vertex=0
t_f10=[]
rank10=0
row10=[-1]*N
f21=[0]*M
rank21=0
row21=[-1]*M*3
uff_total=UnionFindForest(N)
uff_each=[UnionFindForest(N)for i in R(N)]
edge_num=[[-1]*N for i in R(N)]
e=[[]for i in R(N)]
for m in R(M):
    ABC=[x-1 for x in J()]
    for i in ABC:
        if not appeared[i]:
            appeared[i]=1
            vertex+=1
    for r in R(3):
        A,B=ABC[1 if r==1 else 0],ABC[1 if r==0 else 2]
        if edge_num[A][B]==-1:
            num=edge_num[A][B]=len(t_f10)
            e[A]+=[B]
            e[B]+=[A]
            t_f10+=[(1<<A)|(1<<B)]
            for j in R(A,N):
                if t_f10[num]>>j&1:
                    if row10[j]==-1:
                        rank10+=1
                        row10[j]=num
                        break
                    else:t_f10[num]^=t_f10[row10[j]]
            uff_total.Graft(A,B)
            for i in R(N):
                if i!=A and i!=B:uff_each[i].Graft(A,B)
        f21[m]|=1<<edge_num[A][B]
    for j in R(len(t_f10)):
        if f21[m]>>j&1:
            if row21[j]==-1:
                rank21+=1
                row21[j]=m
                break
            else:f21[m]^=f21[row21[j]]
    if uff_total.RootSize()-(N-vertex)!=1:print("CO")
    elif len(t_f10)-rank10>rank21:print("H1")
    else:
        LK=1
        for i in R(N):
            if appeared[i]:
                root=uff_each[i].RootOfNode(e[i][0])
                for j in R(1,len(e[i])):LK&=uff_each[i].RootOfNode(e[i][j])==root
        print("LCKM"[LK::2])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0