Submission #383623

#	Time	Username	Problem	Language	Result	Execution time	Memory
383623		haboh	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	2646 ms	28908 KiB

politicaldevelopment

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <memory.h>
#include <set>

using namespace std;

#define rep(i, n) for(int i =0;i<(n);i++)
#define per(i, n) for (int i=((int)n-1);i>=0;i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define make_unique(x) { sort(all(x)); x.resize(unique(x.begin(), x.end()) - x.begin()); }
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define add insert
#define debug(x) { cerr << #x << "= " << x << "\n"; }
typedef long long ll;
typedef vector<int>vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;

const int N = 50000;
set<int> g[N];


int max_click(vi v) {
	int res = 0;
	for (int mask = 1; mask < (1 << sz(v)); mask++) {
		vi u;
		rep(i, sz(v)) {
			if (mask & (1 << i)) {
				u.pb(v[i]);
			}
		}
		bool ok = true;
		rep(i, sz(u)) {
			for (int j = i + 1; j < sz(u); j++) {
				if (g[u[i]].count(u[j]) == 0) {
					ok = false;
				}
			}
		}
		if (ok) {
			res = max(res, sz(u));
		}
	}
	return res;
}

int main() {
	int n, k;
	cin >> n >> k;
	rep(i, n) {
		int d;
		cin >> d;
		rep(j, d) {
			int x;
			cin >> x;
			g[i].add(x);
		}
	}
	set<pii> bdeg;
	rep(i, n) {
		bdeg.add({ sz(g[i]), i });
	}
	int ans = 0;
	while (sz(bdeg)) {
		int v = bdeg.begin()->ss;
		bdeg.erase(bdeg.begin());
		vi cand;
		for (int u : g[v]) {
			cand.pb(u);
		}
		cand.pb(v);

		ans = max(ans, max_click(cand));

		for (int u : g[v]) {
			bdeg.erase(mp(sz(g[u]), u));
			g[u].erase(v);
			bdeg.add(mp(sz(g[u]), u));
		}
	}
	cout << ans;
	return 0;
}

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