Submission #469782

#	Time	Username	Problem	Language	Result	Execution time	Memory
469782		tutis	Split the Attractions (IOI19_split)	C++17	40 / 100	125 ms	22980 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;
	pair<int, int>cen = {n + 1, 0};
	function<void(int)>dfs1 = [&](int x)->void
	{
		int mx = n - sz[x];
		for (int y : child[x])
		{
			mx = max(mx, sz[y]);
			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;
			}
		}
		cen = min(cen, {mx, x});
	};
	dfs1(0);
	if (gal == -1)
	{
		int c = cen.second;
		vector<int>com(n, 1);
		int dyd[n];
		com[c] = 0;
		int timer = 2;
		dyd[0] = 1;
		dyd[1] = n - sz[c];
		for (int a : child[c])
		{
			dyd[a] = sz[a];
			function<void(int)>dfs2 = [&](int x)->void
			{
				com[x] = timer;
				for (int y : child[x])
				{
					dfs2(y);
				}
			};
			dfs2(a);
			timer++;
		}
		int pa[n];
		for (int i = 0; i < n; i++)
			pa[i] = i;
		function<int(int)>root = [&](int x)
		{
			if (x == pa[x])
				return x;
			return pa[x] = root(pa[x]);
		};
		int spalv[n];
		for (int i = 0; i < n; i++)
		{
			for (int j : adj[i])
			{
				int a = root(com[i]);
				int b = root(com[j]);
				if (a != b && a != 0 && b != 0)
				{
					pa[a] = b;
					dyd[b] += dyd[a];
					if (dyd[b] >= C[0].first)
					{
						int cnt0 = 0;
						int cnt1 = 0;
						for (int i = 0; i < n; i++)
						{
							if (root(i) == b)
							{
								spalv[i] = 0;
								cnt0++;
							}
							else
							{
								spalv[i] = 1;
								cnt1++;
							}
						}
						int k0 = 0;
						int k1 = 0;
						if (cnt0 >= C[0].first && cnt1 >= C[1].first)
						{
							while (spalv[k0] != 0)
								k0++;
							while (spalv[k1] != 1)
								k1++;
						}
						else if (cnt1 >= C[0].first && cnt0 >= C[1].first)
						{
							while (spalv[k0] != 1)
								k0++;
							while (spalv[k1] != 0)
								k1++;
						}
						else {
							assert(false);
						}

						function<void(int, int, int&)>dfs3 = [&](int x, int col, int &cnt)->void
						{
							if (cnt <= 0)
								return;
							cnt--;
							res[x] = C[col].second;
							for (int y : adj[x])
							{
								if (spalv[y] != spalv[x])
									continue;
								if (res[y] == C[2].second)
									dfs3(y, col, cnt);
							}
						};
						dfs3(k0, 0, C[0].first);
						dfs3(k1, 1, C[1].first);
						return res;
					}
				}
			}
		}
		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