Submission #1251208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251208		kaiboy	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	47 ms	3660 KiB

politicaldevelopment

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 50000;
const int M = 10;

int *ej[N], eo[N], dd[N], qu[N], ii[N], kk[1 << M];
bool aa[M][M], dp[1 << M], dq[1 << M];

bool check(int i, int j) {
	int lower = -1, upper = eo[i];
	while (upper - lower > 1) {
		int o = lower + upper >> 1;
		if (ej[i][o] <= j)
			lower = o;
		else
			upper = o;
	}
	int o = lower;
	return o >= 0 && ej[i][o] == j;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, d_; cin >> n >> d_, d_--;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int d; cin >> d, eo[i] = dd[i] = d;
		ej[i] = new int[d];
		for (int o = 0; o < d; o++) {
			int j; cin >> j;
			ej[i][o] = j;
		}
		sort(ej[i], ej[i] + d);
		if (d <= d_)
			qu[cnt++] = i;
	}
	int k = 0;
	for (int b = 1; b < 1 << d_; b++)
		kk[b] = kk[b & b - 1] + 1;
	while (cnt) {
		int i = qu[--cnt], m = 0; dd[i] = -1;
		for (int o = 0; o < eo[i]; o++) {
			int j = ej[i][o];
			if (dd[j] != -1)
				ii[m++] = j;
		}
		for (int h = 0; h < m; h++) {
			aa[h][h] = true;
			for (int g = h + 1; g < m; g++)
				aa[h][g] = check(ii[h], ii[g]);
		}
		dp[0] = dq[0] = true;
		for (int b = 1, h = 0; b < 1 << m; b++) {
			if (1 << h + 1 <= b)
				h++;
			int b_ = b & b - 1, h_ = kk[(b & -b) - 1];
			dq[b] = aa[h_][h] && dq[b_];
			dp[b] = dq[b] && dp[b ^ 1 << h];
			if (dp[b])
				k = max(k, kk[b]);
		}
		for (int h = 0; h < m; h++) {
			int j = ii[h];
			if (--dd[j] == d_)
				qu[cnt++] = j;
		}
	}
	cout << k + 1 << '\n';
	return 0;
}

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