Submission #478057

#	Time	Username	Problem	Language	Result	Execution time	Memory
478057		Sohsoh84	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	431 ms	74312 KiB

politicaldevelopment

// ?
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;

set<int> adj[MAXN];
set<pll> st;
int n, k, ans = 1, msk_adj[MAXN];
bool dp[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int d;
		cin >> d;
		for (int j = 1; j <= d; j++) {
			int v;
			cin >> v;
			v++;
			adj[i].insert(v);
		}
		
		st.insert({adj[i].size(), i});
	}

	while (!st.empty()) {
		int v = st.begin() -> Y;
		st.erase(st.begin());

		vector<int> vec;
		for (int e : adj[v]) {
			st.erase({adj[e].size(), e});
			adj[e].erase(v);
			vec.push_back(e);
			st.insert({adj[e].size(), e});
		}

		int sz = vec.size();
		for (int i = 0; i < sz; i++)
			for (int j = 0; j < sz; j++)
				msk_adj[i] ^= (adj[vec[i]].find(vec[j]) == adj[vec[i]].end() ? 0 : (1 << j));

		dp[0] = true;
		for (int msk = 1; msk < (1 << sz); msk++) {
			int ind = __builtin_ctz(msk), tmsk = msk - (1 << ind);
			dp[msk] = (dp[tmsk] && (tmsk & msk_adj[ind]) == tmsk);
		
			if (dp[msk]) ans = max(ans, __builtin_popcount(msk) + 1);
		}

		for (int i = 0; i < sz; i++) msk_adj[i] = 0;

	}

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

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