Submission #469774

#	Time	Username	Problem	Language	Result	Execution time	Memory
469774		tutis	Split the Attractions (IOI19_split)	C++17	40 / 100	125 ms	23108 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);
		com[c] = 0;
		int timer = 2;
		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++;
		}
		set<int>jun[n];
		for (int i = 0; i < n; i++)
		{
			for (int j : adj[i])
			{
				if (com[i] != com[j] && com[i] != 0 && com[j] != 0)
				{
					jun[com[i]].insert(com[j]);
					jun[com[j]].insert(com[i]);
				}
			}
		}
		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