hogloidのブログ

へなちょこ

PKU 2443 Set Operation

なんか苦戦したので書きます
C(i)(<=10000)個の数の集合がN(<=1000)個あって、Q(<=200000)個のクエリでa,bが与えられ、a,bがどれか一つでも同じ集合に含まれているかどうかを判別します。
数はすべて10000以下

最初はソートしようかな、とか思ったけどソートすらTLEになりそう
数が1万以下なので普通に配列にもつ
O(CN+QN)でいいかな?ー>TLE
数が1万以下だからあらかじめ求めておいた方が良さそう
bitset初めて使うー>AC
ビットセットというだけあってビット演算はやいですね

bitset<10001>buf[1001];
bitset<10001> united[10001];
int main(){
	int n;scanf("%d",&n);
	REP(i,n){
		int c;scanf("%d",&c);
		REP(j,c){
			int t;scanf("%d",&t);
			buf[i][t]=true;
		}
	}
	REP(i,10001){
		REP(j,n){
			if(buf[j][i]){
				united[i]|=buf[j];
			}
		}
	}
	int q;scanf("%d",&q);
	REP(i,q){
		int a,b;scanf("%d%d",&a,&b);
		if(united[a][b]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}