Submission #1005769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005769		12345678	Split the Attractions (IOI19_split)	C++17	29 / 100	488 ms	1048576 KiB

split

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

using namespace std;

const int nx=1e5+5;

int N, sz[nx], f, cnt;
vector<int> d[nx], res;
vector<pair<int, int>> t;

void dfs2(int u, int p, int x)
{
	res[u]=x;
	cnt--;
	for (auto v:d[u]) if (v!=p&&cnt>0) dfs2(v, u, x);
}
void dfs(int u, int p)
{
	sz[u]=1;
	for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
	if (p!=u&&!f&&min(sz[u], N-sz[u])>=t[0].first&&max(sz[u], N-sz[u])>=t[1].first) 
	{
		int a=sz[u], b=N-sz[u];
		f=1;
		if (a<=b)
		{
			cnt=t[0].first;
			dfs2(u, p, t[0].second);
			cnt=t[1].first;
			dfs2(p, u, t[1].second);
		}
		else
		{
			cnt=t[0].first;
			dfs2(p, u, t[0].second);
			cnt=t[1].first;
			dfs2(u, p, t[1].second);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	res.resize(n);
	t.push_back({a, 1}), t.push_back({b, 2}), t.push_back({c, 3});
	sort(t.begin(), t.end());
	for (int i=0; i<n-1; i++) d[p[i]].push_back(q[i]), d[q[i]].push_back(p[i]);
	dfs(0, 0);
	if (f) for (int i=0; i<N; i++) if (res[i]==0) res[i]=t[2].second;
	return res;
}

/*
5 4
1 2 2
0 1
0 2
0 3
0 4
*/

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