CSAcademy Round #79 : D. Groups

これ通っていいんだ。
https://csacademy.com/contest/round-79/task/groups/

問題

N人の人がK個のグループを組んでいる。
各人複数のグループに属することができるが、グループの代表者だけは1個のグループにしか属せない。

人の番号の集合からなるクエリが与えられる。
グループ内の全員がその集合に属するようなグループ数を求めよ。

解法

クエリを代表者とそうでない人に分けよう。
代表者毎に、対応するグループについてグループ内の代表者以外の集合がクエリの人の集合に含まれるか地道に判定すればよい。
平方分割とかいるかと思ったけど、なくても間に合った。

int N,K,Q;
int R[101010];
vector<int> V[101010];
int rev[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(rev);
	
	cin>>N>>K>>Q;
	FOR(i,K) {
		cin>>x;
		cin>>R[i];
		rev[R[i]]=i;
		
		x--;
		while(x--) {
			cin>>y;
			V[i].push_back(y);
		}
		sort(ALL(V[i]));
	}
	
	FOR(i,Q) {
		cin>>x;
		vector<int> A,B;
		FOR(j,x) {
			cin>>y;
			if(rev[y]>=0) A.push_back(rev[y]);
			else B.push_back(y);
		}
		sort(ALL(B));
		
		int ret=0;
		FORR(r,A) {
			if(V[r].size()<=B.size()) {
				x=0;
				FORR(b,B) {
					if(x==V[r].size()) break;
					if(V[r][x]==b) x++;
				}
				if(x==V[r].size()) ret++;
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

なんだこの問題。