結果

問題 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])
0