Submission #469809

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

split

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

vector<int> find_split(int n, int c1, int c2, int c3, vector<int> p, vector<int> q) {
	pair<int, int>C[3] = {{c1, 1}, {c2, 2}, {c3, 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);
	assert(cen.first * 2 <= n);
	if (gal == -1)
	{
		int c = cen.second;
		vector<int>com(n, 1);
		com[c] = 0;
		int timer = 2;
		if (sz[c] == n)
			timer = 1;
		vector<int>dyd(n, 0);
		int pa[n];
		function<int(int)>root = [&](int x)
		{
			if (x == pa[x])
				return x;
			return pa[x] = root(pa[x]);
		};
		for (int a : child[c])
		{
			// function<void(int)>dfs2 = [&](int x)->void
			// {
			// 	com[x] = timer;
			// 	for (int y : child[x])
			// 	{
			// 		dfs2(y);
			// 	}
			// };
			// dfs2(a);
			timer++;
		}
		assert(timer <= n);
		// for (int i = 0; i < n; i++)
		// 	dyd[com[i]]++;
		// for (int i = 0; i < n; i++)
		// 	pa[i] = i;
		// for (int i = 0; i < n; i++)
		// {
		// 	assert(dyd[i] < C[0].first || dyd[i] > C[1].first);
		// }
		int spalv[n];
		if (false)
			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(com[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++;
							}
							assert(k0 != k1);

							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;
}
// int main()
// {
// 	for (int i : find_split(9, 3, 3, 3, {0, 1, 2, 3, 4, 5, 6, 7, 8}, {8, 0, 1, 2, 3, 4, 5, 6, 7}))
// 	{
// 		cout << i << " ";
// 	}
// }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:74:12: warning: unused variable 'a' [-Wunused-variable]
   74 |   for (int a : child[c])
      |            ^

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