結果

問題 No.3034 コーエン-マコーレー抽象単体複体
ユーザー TKTYI
提出日時 2025-02-21 23:49:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,805 bytes
コンパイル時間 5,000 ms
コンパイル使用メモリ 313,584 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2025-02-21 23:49:48
合計ジャッジ時間 8,470 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other AC * 2 WA * 2 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const ll mod=998244353;
struct dsu{
	vector<int>nec;
	dsu(int N):nec(N,-1){}
	int leader(int v){while(nec[v]>=0)v=nec[v];return v;}
	int size(int v){return -nec[leader(v)];}
	int merge(int u,int v){
		u=leader(u);
		v=leader(v);
		if(u==v)return u;
		if(nec[u]<nec[v])swap(u,v);
		nec[v]+=nec[u];
		nec[u]=v;
		return v;
	}
};
bool LK(vi A,vi B,vi C){
	set<int>V;
	for(auto a:A)V.insert(a);
	for(auto b:B)V.insert(b);
	for(auto c:C)V.insert(c);
	vector<vector<int>>E(1000);
	vector<vector<pii>>F(1000);
	int M=sz(A);
	rep(i,0,M){
		E[A[i]].emplace_back(B[i]);
		E[A[i]].emplace_back(C[i]);
		E[B[i]].emplace_back(C[i]);
		E[B[i]].emplace_back(A[i]);
		E[C[i]].emplace_back(A[i]);
		E[C[i]].emplace_back(B[i]);
		F[A[i]].emplace_back(pii(B[i],C[i]));
		F[B[i]].emplace_back(pii(A[i],C[i]));
		F[C[i]].emplace_back(pii(A[i],B[i]));
	}
	vi rev(1000);
	for(auto v:V){
		vi U;
		for(auto u:E[v])U.emplace_back(u);
		sort(all(U));
		U.erase(unique(all(U)),U.end());
		rep(i,0,sz(U))rev[U[i]]=i;
		dsu DSU(sz(U));
		for(auto[a,b]:F[v])DSU.merge(rev[a],rev[b]);
		if(DSU.size(0)!=sz(U))return false;
	}
	return true;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int N,M;cin>>N>>M;
	
	vector<int>_A(M),_B(M),_C(M);
	rep(i,0,M)cin>>_A[i]>>_B[i]>>_C[i];
	vector<pii>_E;
	rep(i,0,M){
		rep(_,0,3){
			_E.emplace_back(pii(min(_A[i],_B[i]),max(_A[i],_B[i])));
			swap(_A[i],_B[i]);swap(_B[i],_C[i]);
		}
	}
	sort(all(_E));
	_E.erase(unique(all(_E)),_E.end());
	
	dsu D(N);
	set<int>V;
	set<pii>E;
	vector<int>A,B,C;
	vector<pair<bitset<3000>,int>>base1,base2;
	rep(_,0,M){
		int a=_A[_],b=_B[_],c=_C[_];
		A.emplace_back(a);
		B.emplace_back(b);
		C.emplace_back(c);
		D.merge(a,b);
		D.merge(a,c);
		V.insert(a);
		V.insert(b);
		V.insert(c);
		rep(_,0,3){
			if(!E.count(pii(min(a,b),max(a,b)))){
				E.insert(pii(min(a,b),max(a,b)));
				bitset<3000>Q;
				Q[a]=Q[b]=1;
				for(auto[b,c]:base1)if(Q[c])Q=Q^b;
				if(Q.any()){
					int a=0;
					while(!Q[a])a++;
					base1.emplace_back(make_pair(Q,a));
				}
			}
			swap(a,b);
			swap(b,c);
		}
		{
			bitset<3000>Q;
			Q[lower_bound(all(_E),pii(a,b))-_E.begin()]=1;
			Q[lower_bound(all(_E),pii(b,c))-_E.begin()]=1;
			Q[lower_bound(all(_E),pii(a,c))-_E.begin()]=1;
				for(auto[b,c]:base2)if(Q[c])Q=Q^b;
				if(Q.any()){
					int a=0;
					while(!Q[a])a++;
					base2.emplace_back(make_pair(Q,a));
				}
			swap(a,b);
			swap(b,c);
		}
		
		if(D.size(a)!=sz(V)){cout<<"CO"<<endl;continue;}
		else if(sz(base1)==sz(base2))cout<<"H1"<<endl;
		else if(!LK(A,B,C))cout<<"LK"<<endl;
		else cout<<"CM"<<endl;
	}
}
0