Submission #427021

#	Time	Username	Problem	Language	Result	Execution time	Memory
427021		saleh	Split the Attractions (IOI19_split)	C++17	40 / 100	150 ms	14980 KiB

split

#include "split.h"
#include <bits/stdc++.h>

#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23;


int zz = -1, cc, sz[MAXN], par[MAXN];
vector<int> res;
bitset<MAXN> mark;
vector<int> g[MAXN];

void dfsa(int v) {
	mark[v] = true;
	zz = v;
	cc--;
	for (auto i : g[v]) if (!mark[i] && cc != 0) dfsa(i);
}
int sfs(int v = 0, int p = -1) {
	par[v] = p;
	for (auto i : g[v]) if (i != p) sz[v] += sfs(i, v);
	return ++sz[v];
}
void mfs(int v, int p, int c) {
	res[v] = c;
	cc--;
	for (int i : g[v]) if (i != p && cc > 0) mfs(i, v, c);
}
void cfs(int v, int c) {
	mark[v] = true;
	cc--;
	res[v] = c;
	for (auto i : g[v]) if (!mark[i] && cc != 0) cfs(i, c);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = p.size();
	for (int i = 0; i < m; i++) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
	if (a == 1) {
		for (int i = 0; i < n; i++) res.push_back(3);
		cc = b + 1;
		dfsa(0);
		for (int i = 0; i < n; i++) if (mark[i]) res[i] = 2;
		res[zz] = 1;
		return res;
	}
	if (m == n) {
		for (int i = 0; i < n; i++) res.push_back(0);
		cc = a;
		cfs(0, 1);
		for (int i = 0; i < n; i++) if (!mark[i]) {
			cc = b;
			cfs(i, 2);
			break;
		}
		for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = 3;
		return res;
	}
	if (m == n - 1) {
//		exit(3);
		for (int i = 0; i < n; i++) res.push_back(0);
		vector<pii> o = {{a, 1}, {b, 2}, {c, 3}};
		sort(o.begin(), o.end());
		int f = min({a, b, c}), g = max({min(a, b), min(b, c), min(c, a)});
		sfs();
		for (int i = 1; i < n; i++) if (sz[i] >= f && n - sz[i] >= g) {
			cc = f;
			mfs(i, par[i], o[0].sd);
			cc = g;
			mfs(par[i], i, o[1].sd);
			for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd;
			break;
		} else if (sz[i] >= g && n - sz[i] >= f) {
			cc = g;
			mfs(i, par[i], o[1].sd);
			cc = f;
			mfs(par[i], i, o[0].sd);
			for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd;
			break;
		}
		return res;
	}
	return res;
}

//int main() {}

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