Submission #1217801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217801		HappyCapybara	Split the Attractions (IOI19_split)	C++17	100 / 100	80 ms	24136 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;

int cnt;
vector<int> st, num, low;
vector<vector<int>> g, tc;
vector<int> res;
vector<bool> fts;

void dfs(int cur){
	num[cur] = cnt;
	cnt++;
	low[cur] = num[cur];
	st[cur] = 1;
	for (int next : g[cur]){
		if (num[next] != -1){
			low[cur] = min(low[cur], num[next]);
			continue;
		}
		dfs(next);
		low[cur] = min(low[cur], low[next]);
		st[cur] += st[next];
		tc[cur].push_back(next);
	}
}

int fill(int cur, int x, int c, bool b){
	if (res[cur] == c) return 0;
	if (x <= 0) return 0;
	if (fts[cur] != b) return 0;
	res[cur] = c;
	int done = 1;
	for (int next : g[cur]) done += fill(next, x-done, c, b);
	return done;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	int m = p.size();
	g.resize(n);
	for (int i=0; i<m; i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	tc.resize(n);
	st.resize(n);
	num.resize(n, -1);
	low.resize(n);
	cnt = 0;
	dfs(0);
	vector<int> cc = {a, b, c}, ccc = {1, 2, 3};
	if (cc[0] > cc[1]){
		swap(cc[0], cc[1]);
		swap(ccc[0], ccc[1]);
	}
	if (cc[1] > cc[2]){
		swap(cc[1], cc[2]);
		swap(ccc[1], ccc[2]);
	}
	if (cc[0] > cc[1]){
		swap(cc[0], cc[1]);
		swap(ccc[0], ccc[1]);
	}
	int v;
	for (int i=0; i<n; i++){
		if (st[i] < cc[0]) continue;
		bool valid = true;
		for (int next : tc[i]){
			if (st[next] >= cc[0]) valid = false;
		}
		if (!valid) continue;
		v = i;
		break;
	}
	int s1 = st[v], s2 = n-st[v];
	set<int> rem;
	for (int next : tc[v]){
		if (low[next] < num[v] && s1-st[next] >= cc[0]){
			rem.insert(next);
			s1 -= st[next];
			s2 += st[next];
		}
	}
	fts.resize(n, false);
	stack<int> stk;
	stk.push(v);
	while (!stk.empty()){
		int cur = stk.top();
		stk.pop();
		if (rem.find(cur) != rem.end()) continue;
		fts[cur] = true;
		for (int next : tc[cur]) stk.push(next);
	}
	if (s1 >= cc[0] && s2 >= cc[1]){
		res.assign(n, ccc[2]);
		fill(v, cc[0], ccc[0], true);
		fill(0, cc[1], ccc[1], false);
		return res;
	}
	else if (s1 >= cc[1] && s2 >= cc[0]){
		res.assign(n, ccc[2]);
		fill(v, cc[1], ccc[1], true);
		fill(0, cc[0], ccc[0], false);
		return res;
	}
	else return vector<int>(n, 0);
}

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