Codeforces #561 Div2 E. The LCMs Must be Large

気づけば実装はラク。
https://codeforces.com/contest/1166/problem/E

問題

ある整数列Aがあるが中身は不明である。

M通りのBに対し以下が達成できるようなAが存在するか。

• AのsubsetがB[i]与えられる。LCM(B[i])＞LCM(A-B[i])である。

解法

LCM(B[i])＞LCM(A-B[i])なので、B[i]⊆A-B[j]となってはならない。
こうなるとB[i]⊆A-B[j]⊆B[j]⊆A-B[i]となり、Aの値が何であれ矛盾が生じる。

後は上記判定をbitsetで行う。

int N,M;
bitset<10101> B[51],C[51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N;
	FOR(i,M) FOR(j,N) C[i][j]=1;
	FOR(i,M) {
		cin>>x;
		FOR(j,x) {
			cin>>y;
			y--;
			B[i][y]=1;
			C[i][y]=0;
		}
	}
	
	FOR(x,M) FOR(y,M) {
		if((C[y]&B[x])==B[x]) return _P("impossible\n");
	}
	cout<<"possible"<<endl;
	
}

まとめ

本番結構時間かかってるな。