Submission #333215

#	Time	Username	Problem	Language	Result	Execution time	Memory
333215		limabeans	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1240 ms	26860 KiB

politicaldevelopment

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 5e4 + 10;


int n,k;
set<int> g[maxn];

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

    cin>>n>>k;

    for (int i=0; i<n; i++) {
	int t;
	cin>>t;
	while (t--) {
	    int x;
	    cin>>x;
	    g[i].insert(x);
	    g[x].insert(i);
	}
    }


    queue<int> qq;
    vector<bool> added(n, false);


    for (int i=0; i<n; i++) {
	if ((int)g[i].size()<k) {
	    qq.push(i);
	    added[i] = true;
	}
    }
    
    int ans = 0;

    while (qq.size()) {
	int at = qq.front();
	qq.pop();
	int len = g[at].size();
	for (int mask=0; mask<(1<<len); mask++) {
	    int val = __builtin_popcount(mask);
	    if (val <= ans) {
		continue;
	    }
	    int tmp = mask;
	    vector<int> w;
	    for (int x: g[at]) {
		if (tmp&1) {
		    w.push_back(x);
		}
		tmp >>= 1;
	    }

	    int N = w.size();
	    bool ok = true;
	    for (int i=0; i<N && ok; i++) {
		for (int j=i+1; j<N && ok; j++) {
		    ok &= (g[w[i]].count(w[j]));
		}
	    }

	    if (ok) {
		ans = max(ans, val);
	    }
	}

	for (int to: g[at]) {
	    g[to].erase(at);
	    if ((int)g[to].size()<k && !added[to]) {
		qq.push(to);
	    }
	}
	g[at].clear();
    }


    cout<<ans+1<<endl;    
    return 0;
}

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