Submission #758192

#	Time	Username	Problem	Language	Result	Execution time	Memory
758192		MetalPower	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	1175 ms	70396 KiB

politicaldevelopment

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

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;

int N, K, vis[MX], sz[MX]; map<pii, int> mp;
vector<int> adj[MX];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int solve(int x){
	vector<int> kew;
	for(int nx : adj[x]){
		if(vis[nx]) continue;
		kew.push_back(nx);
	}

	int ns = kew.size(), mk = 1 << ns, ans = 0;

	for(int mask = 0; mask < mk; mask++){
		int num = 1;
		bool curr = true;
		for(int j = 0; j < ns; j++){
			if((mask >> j & 1) != 1) continue;
			num++;
			if(!mp[make_pair(x, kew[j])]){
				curr = false;
				break;
			}
			for(int k = j + 1; k < ns; k++){
				if((mask >> k & 1) != 1) continue;
				if(!mp[make_pair(kew[k], kew[j])]){
					curr = false;
					break;
				}
			}
		}
		if(curr) ans = max(ans, num);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> K;
	for(int i = 0; i < N; i++){
		int v; cin >> sz[i];
		for(int j = 0; j < sz[i]; j++){
			cin >> v;
			adj[i].push_back(v);
			mp[make_pair(i, v)] = 1;
		}
	}

	for(int i = 0; i < N; i++) pq.push({sz[i], i});

	int mx = 1;
	for(;!pq.empty();){
		int curr = pq.top().se; pq.pop();
		if(vis[curr]) continue;
		mx = max(mx, solve(curr));
		vis[curr] = 1;
		for(int nx : adj[curr]){
			if(!vis[nx]){
				sz[nx]--;
				pq.push({sz[nx], nx});
			}
		}
	}
	cout << mx << '\n';
}

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