Submission #667136

#	Time	Username	Problem	Language	Result	Execution time	Memory
667136		flappybird	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	748 ms	37496 KiB

politicaldevelopment

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MK 11
vector<int> adj[MAX], add[MAX];
int deg[MAX];
int ord[MAX];
int mp[MK][MK];
int dp[1 << MK];
int bcnt[1 << MK];
int ans = 1;
int valid[MK];
int vis[MAX];
set<pii> alledge;
bool ison[MAX];
void calc(int N) {
	if (!N) return;
	ans = max(ans, 2);
	dp[0] = 1;
	dp[1] = 1;
	int i, j;
	for (i = 1; i < N; i++) {
		int mask = 0;
		for (j = i - 1; j >= 0; j--) {
			mask <<= 1;
			if (mp[i][j]) mask |= 1;
		}
		for (j = 0; j < (1 << i); j++) {
			if (dp[j] && (mask & j) == j) dp[1 << i | j] = 1, ans = max(ans, bcnt[1 << i | j] + 1);
			else dp[1 << i | j] = 0;
		}
	}
}
bool chk(int a, int b) {
	if (alledge.find(pii(a, b)) != alledge.end()) return true;
	if (alledge.find(pii(b, a)) != alledge.end()) return true;
	else return false;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	cin >> N >> K;
	int i, j, k, a;
	for (i = 0; i < (1 << MK); i++) {
		a = i;
		while (a) {
			bcnt[i] += a & 1;
			a >>= 1;
		}
	}
	queue<int> q;
	for (i = 0; i < N; i++) {
		cin >> deg[i];
		for (j = 0; j < deg[i]; j++) cin >> a, adj[i].push_back(a), alledge.emplace(a, i);
		if (deg[i] < K) q.push(i);
	}
	int cnt = 0;
	while (q.size()) {
		int t = q.front();
		q.pop();
		if (vis[t]) continue;
		vis[t] = 1;
		ord[cnt++] = t;
		for (auto v : adj[t]) {
			deg[v]--;
			if (!vis[v] && deg[v] < K) q.push(v);
		}
	}
	assert(cnt == N);
	for (i = N - 1; i >= 0; i--) {
		int v = ord[i];
		ison[v] = true;
		for (auto x : adj[v]) if (ison[x]) add[v].push_back(x);
		for (j = 0; j < add[v].size(); j++) {
			for (k = j + 1; k < add[v].size(); k++) {
				if (chk(add[v][j], add[v][k])) mp[j][k] = mp[k][j] = 1;
				else mp[j][k] = mp[k][j] = 0;
			}
		}
		assert(add[v].size()<=11);
		calc(add[v].size());
	}
	cout << ans << ln;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (j = 0; j < add[v].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for (k = j + 1; k < add[v].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~~

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