Submission #1290808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290808		kahoul	Split the Attractions (IOI19_split)	C++20	0 / 100	606 ms	1114112 KiB

split

	#include <algorithm>
	#include "split.h"

	const int maxn = 2e5 + 10;
	std::vector<int> rel[maxn];
	int deg[maxn];
	int pai[maxn];

	std::vector<int> res(maxn, 3);
	std::vector<bool> used(maxn, 0);

	int a, b, c;
	int needed = 0;
	int amt = 0;
	int amt_resto = 0;
	int sz[maxn];

	void dfs1 (int u, int p) {
		sz[u] = 1;
		pai[u] = p;

		for (auto v : rel[u]) {
			if (v == p) continue;
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}

	void dfs (int u, int p, int color) {
		if (amt == needed) return;

		used[u] = 1;
		res[u] = color;
		amt++;

		for (auto v : rel[u]) {
			if (v == pai[u]) continue;
			if (used[v]) continue;
			if (amt == needed) return;
			dfs(v, u, color);
		}
	}

	void dfs_resto (int u, int p, int color) {
		used[u] = 1;
		res[u] = color;

		for (auto v : rel[u]) {
			if (used[v]) continue;
			dfs_resto(v, u, color);
		}
	}

	std::vector<int> find_split(int n, int A, int B, int C, std::vector<int> p, std::vector<int> q) {
		a = A;
		b = B;
		c = C;

		int cor_real[4];

		for (int i = 0; i < p.size(); i++) {
			int u = p[i];
			int v = q[i];
			rel[u].push_back(v);
			rel[v].push_back(u);
			deg[u]++;
			deg[v]++;
		}

		std::vector<std::pair<int, int>> colors = {{a, 1}, {b, 2}, {c, 3}};
		std::sort(colors.begin(), colors.end());
		cor_real[3] = colors[2].second;

		dfs1(0, 0);

		int pika = -1;
		int cor = -1;
		int cor_dois = -1;

		for (int i = 0; i < n; i++) {
			//std::cerr << sz[i] << ' ';
		}
		//std::cerr << '\n';

		for (int i = 0; i < n; i++) {
			int leftover = sz[0] - sz[i];
			if (colors[0].first <= sz[i] && colors[1].first <= leftover) {
				pika = i;
				cor = 1;
				cor_dois = 2;
				amt = colors[0].first;
				amt_resto = colors[1].first;
				cor_real[1] = colors[0].second;
				cor_real[2] = colors[1].second;
			}
			if (colors[1].first <= sz[i] && colors[0].first <= leftover) {
				pika = i;
				cor = 2;
				cor_dois = 1;
				amt = colors[1].first;
				amt_resto = colors[0].first;
				cor_real[1] = colors[1].second;
				cor_real[2] = colors[0].second;
			}
		}

		if (pika == -1) {
			std::vector<int> ans;

			for (int i = 0; i < n; i++) {
				ans.push_back(0);
			}

			return ans;
		}

		dfs(pika, pika, cor);

		needed = amt_resto;
		amt = 0;

		dfs(0, 0, cor_dois);

		std::vector<int> ans;

		for (int i = 0; i < n; i++) {
			ans.push_back(cor_real[res[i]]);
		}

		return ans;
	}

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