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; }