Submission #551430

#	Time	Username	Problem	Language	Result	Execution time	Memory
551430		blue	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	433 ms	29160 KiB

politicaldevelopment

#include <iostream>
#include <vector>
#include <set>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

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

	int N, K;
	cin >> N >> K;

	set<int> edge[N];

	set<pii> people;

	for(int i = 0; i < N; i++)
	{
		int D;
		cin >> D;

		people.insert({D, i});

		for(int j = 0; j < D; j++)
		{
			int k;
			cin >> k;

			edge[i].insert(k);
		}
	}

	int res = 1;

	// cerr << "check\n";

	vi getlog(100'000, 0);
	for(int i = 0; i < 15; i++)
		getlog[(1<<i)] = i;

	for(int t = 0; t < N; t++)
	{
		// cerr << "t = " << t << '\n';
		int u = people.begin()->second;
		people.erase(people.begin());

		// cerr << "u = " << u << '\n';

		vi currpeople{u};

		for(int v : edge[u])
		{
			currpeople.push_back(v);
		}

		int h = sz(currpeople);

		vi conn(h, 0);
		for(int i = 0; i < h; i++)
		{
			for(int j = i+1; j < h; j++)
			{
				if(edge[currpeople[i]].find(currpeople[j]) != edge[currpeople[i]].end())
				{
					conn[i] |= (1<<j);
					conn[j] |= (1<<i);
				}
			}
		}

		// cerr << "done\n";

		vi clique((1<<h), 0);
		for(int s = 1; s < (1<<h); s++)
		{
			int ss = s&-s;
			int rs = s - ss;	

			if((conn[getlog[ss]] & rs) == rs)
				clique[s] = clique[rs] + 1;

			res = max(res, clique[s]);
		}

		for(int v : edge[u])
		{
			people.erase({sz(edge[v]), v});
			edge[v].erase(u);
			people.insert({sz(edge[v]), v});

		}
	}

	cout << res << '\n';
}

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