Submission #596876

#	Time	Username	Problem	Language	Result	Execution time	Memory
596876		SeDunion	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	527 ms	58664 KiB

politicaldevelopment

#include<bitset>
#include<algorithm>
#include<iostream>
#include<set>
#include<vector>

using namespace std;

const int N = 3e5 + 123;

set<int>g[N];
vector<int>vec;

int s[N];

vector<int>can;

int em[N];

#define cerr if(false) cerr

int was[N];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0 ; i < n ; ++ i) {
		cin >> s[i];
		for (int j = 0 ; j < s[i] ; ++ j) {
			int x;
			cin >> x;
			g[i].insert(x);
		}
		if ((int)g[i].size() <= k) {
			was[i] = 1;
			can.emplace_back(i);
		}
	}
	int ans = 0;
	for (int i : can) {
		vec = {i};
		for (auto it : g[i]) vec.emplace_back(it);
		sort(vec.begin(), vec.end());
		vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
		int m = vec.size();
		for (int x = 0 ; x < m ; ++ x) em[x] = 0;
		for (int x = 0 ; x < m ; ++ x) {
			em[x] |= 1 << x;
			for (int y = 0 ; y < m ; ++ y) {
				if (g[vec[x]].count(vec[y])) em[x] |= 1 << y;
			}
		}
		for (int mask = 0 ; mask < 1 << m ; ++ mask) {
			bool ok = true;
			for (int x = 0 ; x < m ; ++ x) {
				if (mask >> x & 1) {
					if ((mask & em[x]) != mask) ok = false;
				}
			}
			if (ok) ans = max(ans, __builtin_popcount(mask));
		}
		for (int v : vec) g[v].erase(i);
		for (int v : vec) if ((int)g[v].size() <= k && !was[v]) was[v] = 1, can.emplace_back(v);
		g[i].clear();
	}
	cout << ans;
}

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