Submission #591721

#	Time	Username	Problem	Language	Result	Execution time	Memory
591721		lumibons	Split the Attractions (IOI19_split)	C++17	100 / 100	108 ms	17976 KiB

split

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

using namespace std;

int n, s[4], t[4], c[100100];
vector<int> r, e[100100];

int dfs(int i) {
	r[i] = -1;
	c[i] = 1;
	for (int j : e[i])
		if (!r[j]) {
			int k = dfs(j);
			c[i] += c[j];
			if (c[j] >= s[0])
				return k;
		}
	r[i] = -2;
	return i;
}

void dfst(int i, int cr, int k) {
	if (!s[k])
		return;
	r[i] = t[k];
	s[k]--;
	for (int j : e[i])
		if (r[j] == cr)
			dfst(j, cr, k);
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	n = N;
	s[0] = A; s[1] = B; s[2] = C; s[3] = n;
	t[0] = 1; t[1] = 2; t[2] = 3; t[3] = -3;
	for (int i : {0, 1, 0})
		if (s[i] > s[i + 1])
			swap(s[i], s[i + 1]), swap(t[i], t[i + 1]);
	for (int i = 0; i < (int) p.size(); i++)
		e[p[i]].push_back(q[i]), e[q[i]].push_back(p[i]);
	r.resize(n);
	int k = dfs(0);
	if (k != 0) {
		dfst(k, -2, 3);
		r[k] = -4;
		for (int i = 0; i < n; i++)
			r[i] = min(r[i], -2);
		if (c[k] >= s[1])
			swap(s[0], s[1]), swap(t[0], t[1]);
		r[k] = -4;
		dfst(0, -2, 1);
		for (int i = 0; i < n; i++)
			if (r[i] == t[1])
				for (int j : e[i])
					if (r[j] == -3)
						dfst(j, -3, 1);
		r[k] = -3;
		dfst(k, -3, 0);
	}
	if (s[0] || s[1])
		r.assign(n, 0);
	else
		for (int i = 0; i < n; i++)
			r[i] = r[i] < 1 ? t[2] : r[i];
	return r;
}

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