Submission #298031

#TimeUsernameProblemLanguageResultExecution timeMemory
298031miss_robotPolitical Development (BOI17_politicaldevelopment)C++14
100 / 100
383 ms26672 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...