Submission #298031

#	Time	Username	Problem	Language	Result	Execution time	Memory
298031		miss_robot	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	383 ms	26672 KiB

politicaldevelopment

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n, k, s = 1;
	cin >> n >> k;
	vector< set<int> > g(n);
	vector<int> q;
	for(int i = 0, j, a; i < n; i++){
		cin >> j;
		if(j < k) q.push_back(i);
		while(j--){
			cin >> a;
			g[i].insert(a);
		}
	}
	while(!q.empty()){
		int u = q.back();
		q.pop_back();
		vector<int> p, c(g[u].size());
		for(int i : g[u]) p.push_back(i);
		for(int i = 0; i < (int)g[u].size(); i++)
			for(int j = 0; j < (int)g[u].size(); j++)
				if(g[p[i]].count(p[j]) || i == j) c[i] |= (1<<j);
		for(int i = 1, p; i < 1<<(int)g[u].size(); i++){
			p = 1;
			for(int j = 0; j < (int)g[u].size(); j++)
				if(i&(1<<j) && i != (i&c[j])) p = 0;
			if(p) s = max(s, __builtin_popcount(i)+1);
		}
		for(int j : g[u]){
			g[j].erase(u);
			if((int)g[j].size() == k-1) q.push_back(j);
		}
	}
	cout << s << "\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23