Submission #469760

#	Time	Username	Problem	Language	Result	Execution time	Memory
469760		tutis	Split the Attractions (IOI19_split)	C++17	40 / 100	129 ms	21428 KiB

split

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

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	pair<int, int>C[3] = {{a, 1}, {b, 2}, {c, 3}};
	sort(C, C + 3);
	vector<int> res(n, C[2].second);
	vector<int>adj[n];
	vector<int>child[n];
	for (int i = 0; i < (int)p.size(); i++)
	{
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	vector<bool>vis(n, false);
	int sz[n];
	function<void(int)>dfs0 = [&](int x)->void
	{
		vis[x] = true;
		sz[x] = 1;
		for (int y : adj[x])
		{
			if (!vis[y])
			{
				child[x].push_back(y);
				dfs0(y);
				sz[x] += sz[y];
			}
		}
	};
	dfs0(0);
	int gal = -1;
	int col = -1;
	function<void(int)>dfs1 = [&](int x)->void
	{
		for (int y : child[x])
		{
			dfs1(y);
			if (sz[y] >= C[1].first && n - sz[y] >= C[0].first)
			{
				gal = y;
				col = 1;
			}
			if (sz[y] >= C[0].first && n - sz[y] >= C[1].first)
			{
				gal = y;
				col = 0;
			}
		}
	};
	dfs1(0);
	if (gal == -1)
		return vector<int>(n, 0);
	function<void(int, int, int&)>dfs2 = [&](int x, int col, int &cnt)->void
	{
		if (cnt <= 0)
			return;
		cnt--;
		res[x] = C[col].second;
		for (int y : child[x])
		{
			if (y == gal)
				continue;
			dfs2(y, col, cnt);
		}
	};
	dfs2(gal, col, C[col].first);
	dfs2(0, 1 - col, C[1 - col].first);
	return res;
}

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