Submission #831243

#	Time	Username	Problem	Language	Result	Execution time	Memory
831243		GusterGoose27	Split the Attractions (IOI19_split)	C++17	0 / 100	69 ms	19984 KiB

split

// #pragma GCC optimize("O2,unroll-loops")

#include "split.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5+5;
int n, m;

vector<int> edges[MAXN];
// vector<int> tree[MAXN];

// pii elist[2*MAXN];
vector<int> res;
// bool vis[MAXN];
// int sz[MAXN];
bool is_point[MAXN];
int lp[MAXN];
int depth[MAXN];
bool vis[MAXN];
bool cut[MAXN];
int to_bcc[MAXN];
int sz[MAXN];

vector<int> stck;
vector<vector<int>> bccs;
bool tested[MAXN];
bool fin[MAXN];
bool vis2[MAXN];

void bcc(int cur, int p = -1) {
	stck.push_back(cur);
	vis[cur] = 1;
	int num = 0;
	for (int nxt: edges[cur]) {
		if (nxt == p) continue;
		if (vis[nxt]) {
			if (depth[nxt] < depth[lp[cur]]) lp[cur] = nxt;
			continue;
		}
		depth[nxt] = 1+depth[cur];
		bcc(nxt, cur);
		if ((depth[lp[nxt]] >= depth[cur] && cur != 0) || (cur == 0 && num)) {
			cut[cur] = 1;
			int p;
			vector<int> v;
			do {
				p = stck.back();
				stck.pop_back();
				v.push_back(p);
				to_bcc[p] = bccs.size();
			} while (p != nxt);
			v.push_back(cur);
			to_bcc[cur] = bccs.size();
			bccs.push_back(v);
		}
		if (depth[lp[nxt]] < depth[lp[cur]]) lp[cur] = lp[nxt];
		num++;
	}
	if (cur == 0) {
		vector<int> v;
		while (!stck.empty()) {
			int p = stck.back();
			stck.pop_back();
			v.push_back(p);
			to_bcc[p] = bccs.size();
		}
		bccs.push_back(v);
	}
}

bool cut2[MAXN];

void get_cut(int cur, bool f = 1, int p = -1) {
	vis2[cur] = 1;
	int num = 0;
	for (int nxt: edges[cur]) {
		if (nxt == p || fin[nxt]) continue;
		if (vis2[nxt]) {
			if (depth[nxt] < depth[lp[cur]]) lp[cur] = nxt;
			continue;
		}
		depth[nxt] = 1+depth[cur];
		get_cut(nxt, 0, cur);
		if ((depth[lp[nxt]] >= depth[cur] && !f) || (f && num)) {
			cut2[cur] = 1;
		}
		if (depth[lp[nxt]] < depth[lp[cur]]) lp[cur] = lp[nxt];
		num++;
	}
}

void set_up(int cur) {
	iota(lp, lp+n, 0);
	fill(depth, depth+n, 0);
	fill(cut2, cut2+n, 0);
	fill(vis2, vis2+n, 0);
	get_cut(cur);
}

void dfs(int cur) {
	vis[cur] = 1;
	sz[cur] = 1;
	for (int nxt: edges[cur]) {
		if (vis[nxt]) continue;
		dfs(nxt);
		sz[cur] += sz[nxt];
	}
}
void assign(int cur, bool col, int &a) {
	if (a == 0) return;
	vis[cur] = 1;
	res[cur] = col;
	a--;
	for (int nxt: edges[cur]) {
		if (!vis[nxt]) {
			assign(nxt, col, a);
		}
	}
}

bool within[MAXN];

int test(int cur, int &a, int &b) {
	fill(vis, vis+n, 0);
	// else {
		if (tested[cur]) return 0;
		fill(within, within+n, 0);
		for (int v: bccs[to_bcc[cur]]) {
			tested[v] = 1;
			vis[v] = 1;
			within[v] = 1;
		}
		vector<pii> szs;
		for (int v: bccs[to_bcc[cur]]) {
			if (cut[v]) {
				dfs(v);
				szs.push_back(pii(sz[v], v));
			}
		}
		szs.push_back(pii(0, -1));
		sort(szs.begin(), szs.end());
		// if the biggest thing is too big for b, return 0
		if (n-szs.back().first < a) return 0;
		// always possible otherwise
		if (szs.back().first >= a) {
			fill(vis, vis+n, 0);
			for (int v: bccs[to_bcc[cur]]) {
				vis[v] = 1;
			}
			bool ex = szs.back().first >= b;
			assign(szs.back().second, ex, ex ? b : a);
			for (int v: bccs[to_bcc[cur]]) {
				vis[v] = 0;
			}
			vis[szs.back().second] = 1;
			assign(cur, !ex, ex ? a : b);
		}
		else {
			fill(fin, fin+n, 1);
			for (int v: bccs[to_bcc[cur]]) fin[v] = 0;
			// just add stuff until you exceed b
			for (int v: bccs[to_bcc[cur]]) {
				if (!cut[v]) sz[v] = 1;
			}
			set<int> adj;
			adj.insert(cur);
			fill(vis, vis+n, 0);
			for (int v: bccs[to_bcc[cur]]) vis[v] = 1;
			// for (int v: bccs[to_bcc[cur]]) cerr << v << ' ';
			// cerr << endl;
			int sum = 0;
			while (b > 0) {
				assert(!adj.empty());
				set_up(*(adj.begin()));
				int f = -1;
				for (int v: adj) {
					if (!cut2[v]) {
						f = v;
						break;
					}
				}
				assert(f != -1);
				sum += sz[f];
				assign(f, 1, b);
				adj.erase(f);
				fin[f] = 1;
				for (int nxt: edges[f]) {
					if (fin[nxt] || !within[nxt]) continue;
					adj.insert(nxt);
				}
			}
			if (n-sum < a) exit(0); // enough stuff left
			assert(!adj.empty());
			for (int i = 0; i < n; i++) vis[i] = (res[i] == 1);
			int s_node = *(adj.begin());
			if (!within[s_node] || vis[s_node]) exit(0);
			// assert(s_node != -1);
			assign(s_node, 0, a);
			assert(a == 0);
			assert(b == 0);
		}
		return 2;
	// }
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	m = p.size();
	vector<pii> change({{a, 1}, {b, 2}, {c, 3}});
	sort(change.begin(), change.end());
	a = change[0].first;
	b = change[1].first;
	for (int i = 0; i < m; i++) {
		edges[p[i]].push_back(q[i]);
		edges[q[i]].push_back(p[i]);
		// elist[i] = pii(p[i], q[i]);
	}
	bool f = 0;
	iota(lp, lp+n, 0);
	bcc(0);
	// fill(vis, vis+n, 0);
	res = vector<int>(n, 2);
	for (int i = 0; i < n; i++) {
		int v;
		if (v = test(i, a, b)) {
			if (v == 1) {
				// assert(a == 0);
				// assert(b == 0);
			}
			// cerr << i << '\n';
			f = 1;
			break;
		}
	}
	if (f) for (int i = 0; i < n; i++) res[i] = change[res[i]].second;
	else res = vector<int>(n, 0);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:230:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  230 |   if (v = test(i, a, b)) {
      |       ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36