Submission #925191

#	Time	Username	Problem	Language	Result	Execution time	Memory
925191		resting	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	224 ms	9468 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n, k; cin  >> n >> k;
	vector<vector<int>> adj(n);
	set<pair<int,int>> uwu;
	vector<int> cnt(n);
	vector<int> vis(n, 0);
	for(int i = 0; i < n; i++){
		cin >> cnt[i]; uwu.insert({cnt[i], i});
		adj[i] = vector<int>(cnt[i]);
		for(auto &x : adj[i]) cin >> x;
		sort(adj[i].begin(), adj[i].end()); //yeee
	}
	int ans = 1;
	while(uwu.size()){
		int i = uwu.begin()->second; vis[i] = 1;
		uwu.erase(uwu.begin());
		vector<int> clique = {i};
		for(auto &x : adj[i]){
			if(vis[x]) continue;
			clique.push_back(x);
			uwu.erase({cnt[x], x});
			cnt[x]--;
			uwu.insert({cnt[x], x});
		}
		int sz = clique.size();
		vector<vector<int>> adj2(sz, vector<int>(sz, 0));
		for(int i = 0; i < sz; i++){
			for(int j = 0; j < sz; j++){
				int i2 = clique[i];
				int j2 = clique[j];
				auto it = lower_bound(adj[i2].begin(), adj[i2].end(), j2);
				if(it != adj[i2].end() && (*it) == j2) adj2[i][j] = 1;
			}
		}
		vector<int> possible((1<<sz), 0);
		vector<int> log2((1<<sz), 0);
		for(int i = 0; i < sz; i++) log2[(1<<i)] = i;
		for(int i = 0; i < (1<<sz); i++){
			if(i==0){possible[i] = 1; continue;}
			int lsb = (i&-i);
			int j = i^lsb;
			possible[i] = possible[j];
			while(j){
				int lsb2 = (j&-j);
				possible[i] &= adj2[log2[lsb]][log2[lsb2]];
				j ^= lsb2;
			}
			if(possible[i]) ans = max(ans, (int)__builtin_popcount(i));
		}
	}
	cout<<ans<<endl;
	
}
signed  main() {
	cin.tie(0)->sync_with_stdio(0);
	int t = 1;// cin >> t;
	while(t--) solve();
}

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