Submission #506153

#	Time	Username	Problem	Language	Result	Execution time	Memory
506153		MilosMilutinovic	Split the Attractions (IOI19_split)	C++14	0 / 100	515 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

using vi=vector<int>;

const int nax=1e5+5;

int n;
int a, b, c;
int ord[4];

vi graf[nax];

int sz[nax];

void dfs_sz(int u, int p)
{
	sz[u]=1;
	for (int v:graf[u])
	{
		if (v==p) continue;
		dfs_sz(v, u);
		sz[u]+=sz[v];
	}
}

int dfsf(int u, int p)
{
	for (int v:graf[u])
	{
		if (v==p) continue;
		if (sz[v]>=2*n)
			return dfsf(v, u);
	}
	return u;
}

int centroid()
{
	dfs_sz(0, 0);
	return dfsf(0, 0);
}

void dfs_down(int u, int p, vi& ans)
{
	if (a==0) return;
	a--;
	assert(ans[u]==0);
	ans[u]=ord[1];
	for (int v:graf[u])
	{
		if (v==p) continue;
		dfs_down(v, u, ans);
	}
}

void dfs_fill2(int u, int p, vi& ans)
{
	if (b==0) return;
	b--;
	assert(ans[u]==0);
	ans[u]=ord[2];
	for (int v:graf[u])
	{
		if (v==p) continue;
		dfs_fill2(v, u, ans);
	}
}

vi find_split(int N, int A, int B, int C, vi u, vi v)
{
	n=N; a=A; b=B; c=C;
	ord[1]=1;
	ord[2]=2;
	ord[3]=3;
	if (a>c)
	{
		swap(a,c);
		swap(ord[1],ord[3]);
	}
	if (b>c)
	{
		swap(b,c);
		swap(ord[2],ord[3]);
	}
	if (a>b)
	{
		swap(a,b);
		swap(ord[1],ord[2]);
	}
	if (a>c)
	{
		swap(a,c);
		swap(ord[1],ord[3]);
	}
	if (b>c)
	{
		swap(b,c);
		swap(ord[2],ord[3]);
	}
	if (a>b)
	{
		swap(a,b);
		swap(ord[1],ord[2]);
	}
	int m=v.size();
	for (int i=0; i<m; i++)
	{
		graf[u[i]].push_back(v[i]);
		graf[v[i]].push_back(u[i]);
	}
	if (m==n-1)
	{
		C=c;
		int c=centroid();
		dfs_sz(c, c);
		for(int v:graf[c])
		{
			if (sz[v]>=a)
			{
				vi ans(n);
				dfs_down(v, c, ans);
				dfs_fill2(c, v, ans);
				for (int i=0; i<n; i++)
				{
					if (ans[i]==0)
					{
						assert(C>0);
						C--;
						ans[i]=ord[3];
					}
				}
				return ans;
			}
		}
		vi ans(n);
		return ans;
	}
}

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:141:1: warning: control reaches end of non-void function [-Wreturn-type]
  141 | }
      | ^

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