Submission #1005756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005756		12345678	Split the Attractions (IOI19_split)	C++17	0 / 100	527 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], t, res;

void dfs2(int u, int p, int x)
{
	if (cnt<=0) return;
	res[u]=x;
	for (auto v:d[u]) if (v!=p) --cnt, 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 (!f&&min(sz[u], N-sz[u])>=t[0]&&max(sz[u], N-sz[u])>=t[1]) 
	{
		int a=sz[u], b=N-sz[u];
		f=1;
		if (a<=b)
		{
			cnt=t[0];
			dfs2(u, p, 1);
			cnt=t[1];
			dfs2(p, u, 2);
		}
		else
		{
			cnt=t[0];
			dfs2(p, u, 1);
			cnt=t[1];
			dfs2(u, p, 2);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	res.resize(n);
	for (int i=0; i<n; i++) res[i]=3;
	t.push_back(a), t.push_back(b), t.push_back(c);
	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++) res[i]=0;
	return res;
}

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

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