Submission #631023

#	Time	Username	Problem	Language	Result	Execution time	Memory
631023		hollwo_pelw	Political Development (BOI17_politicaldevelopment)	C++17	16 / 100	238 ms	26076 KiB

politicaldevelopment

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 5e4 + 5;

int n, k, con[10], dp[1 << 10], res;
set<int> adj[N];

void Hollwo_Pelw(){
	cin >> n >> k;
	set<pair<int, int>> pq;
	for (int i = 0, j, d; i < n; i++) {
		for (cin >> d; d --; )
			cin >> j, adj[i].insert(j);
	}

	for (int i = 0; i < n; i++)
		pq.emplace(adj[i].size(), i);

	while (!pq.empty()) {
		int u = pq.begin() -> second; pq.erase(pq.begin());

		vector<int> f;
		for (int v : adj[u]) {
			f.push_back(v);
			pq.erase({adj[v].size(), v});

			adj[v].erase(u);

			pq.emplace(adj[v].size(), v);
		}

		int m = f.size();
		assert(m <= k);

		fill(dp, dp + (1 << m), 0);

		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++)
				if (adj[f[i]].count(f[j]) || j == i)
					con[i] |= 1 << j;

		dp[0] = 1;

		for (int i = 0; i < m; i++) {
			for (int j = 1 << i; j < 2 << i; j++)
				dp[j] = dp[j ^ 1 << i] & ((con[i] & j) == j);
		}

		for (int j = 0; j < 1 << m; j++) if (dp[j])
			res = max(res, 1 + __builtin_popcount(j));
	}

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

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