Company Organization (AOJ1332)

問題:
1~Nの番号がついた集合がある.集合間の制約が順にM個来るので,どこで最初に矛盾するか答えてください.
制約は5種類で,
1:A⊆B 2:A=B 3:A≠B 4:A∩B=∅ 5:A∩B≠∅
タイプとAとBの番号が制約として与えられる.
N≤100,M≤10000

頭1,実装1,ライブラリ1
簡単だけど注意力がいる

まずにぶたんすればはじめk個の制約で矛盾するかわかればよい.
まず1,2を処理して,包含関係によるposetをつくる(処理した後に推移閉包を取る)
基本的にA∩B=∅ かつ a⊆A かつ b⊆B かつ a∩b≠∅ みたいなペアがなければ矛盾しないから,推移閉包を取った後に4の情報を下に伝播させていく(O(N^4)) でそのあと3,5で矛盾するかどうか確かめる みたいな流れなんだけど,A=∅みたいな形が出てくるのでこれだけでは済まない.例えば,a⊆A b⊆B a∩A=∅ b∩B=∅ みたいなケースだと,a=∅かつb=∅がわかるのでa≠bとは矛盾してしまう.なので∅かどうか みたいなのも持たなければいけない.どういう時にX=∅になるかというと,X⊆A X⊆B A∩B=∅ のとき.これを4を処理するときにO(N)かけてやっておけば全体O(N^4 * log M)で解ける.

頑張ればもうちょっとオーダーよくなりそうだけどどうだろう

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,M,t[10000],v[10000],u[10000];
bool can(int M){
	bool e[100][100]={},emp[10000]={},no[100][100]={};
	rep(i,N) e[i][i]=1;
	rep(i,M){
		if(t[i]==1) e[u[i]][v[i]]=1;
		if(t[i]==2) e[u[i]][v[i]]=e[v[i]][u[i]]=1;
	}
	rep(i,N) rep(j,N) rep(k,N) e[j][k]|=(e[j][i]&&e[i][k]);
	rep(i,M){
		if(t[i]==4){
			int a=v[i],b=u[i];
			rep(c,N) if(e[a][c]&&e[b][c]) emp[c]=1;
			no[a][b]=no[b][a]=1;
		}
	}
	rep(i,N) if(emp[i]){
		rep(j,N) if(e[i][j]) emp[j]=1;
	}
	rep(i,N) rep(j,N) if(no[i][j]){
		rep(I,N) rep(J,N){
			if(e[i][I]&&e[j][J]){
				no[I][J]=1;
			}
		}
	}
	// puts("no");
	// rep(i,N){
	// 	rep(j,N) cout<<no[i][j]<<" ";
	// 	puts("");
	// }
	rep(i,M){
		int a=v[i],b=u[i];
		if(t[i]==3){
			if(emp[a]&&emp[b]) return 0;
			if(e[a][b]&&e[b][a]) return 0;
		}
		if(t[i]==5){
			if(emp[a]||emp[b]) return 0;
			if(no[a][b]) return 0;
		}
	}
	return 1;
}
int main(){
	while(true){
		cin>>N>>M;
		if(N==0) break;
		rep(i,M){
			cin>>t[i]>>v[i]>>u[i],v[i]--,u[i]--;
		}
		int ub=M+1,lb=0;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(can(m)) lb=m;
			else ub=m;
		}
		cout<<lb<<endl;
	}
}