Submission #418635

#	Time	Username	Problem	Language	Result	Execution time	Memory
418635		AdOjis485	Split the Attractions (IOI19_split)	C++14	18 / 100	692 ms	1048580 KiB

split

#include "split.h"
#include <iostream>
#include <algorithm> 

using namespace std;

vector<vector<int> > adi;
vector<int> res;

pair<int, int> ans = {-1, -1};

int dfs(int v, int p, int a, int b, int c)
{
	int count = 1;
	for(int next : adi[v])
	{
		if(next == p) continue;
		count += dfs(next, v, a, b, c);
	}
	if(count >= a && a + b + c - count >= b) ans = {v, p};
	if(count >= b && a + b + c - count >= a) ans = {p, v};
	return count;	
}

void set_ans(int v, int p, int val, int& num)
{
	//cerr << v << " " << p << " " << val << " " << num << '\n'; 
	if(num == 0 || res[v] > 0) return;
	res[v] = val;
	num --;
	for(int next : adi[v]) 
	{
		if(next == p) continue;
		if(p >= 0) p = v;
		set_ans(next, p, val, num);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.assign(n, 0);
	adi.resize(n);
	int m = p.size();
	for(int i = 0; i < m; i ++)
	{
		if(m == n && a > 1 && i == 0) continue;
		adi[p[i]].push_back(q[i]);
		adi[q[i]].push_back(p[i]);
	}


	vector<pair<int, int> > vals = {{a, 1}, {b, 2}, {c, 3}};
	sort(vals.begin(), vals.end());

	if(a == 1)
	{
		int num = b;
		set_ans(0, -1, 2, num);
		bool afound = false;
		for(int i = 0; i < n; i ++)
		{
			if(res[i] == 0)
			{
				if(afound) res[i] = 3;
				else
				{
					afound = true;
					res[i] = 1;
				} 
			}
		}
	}
	else //if(m == n - 1)
	{
		dfs(0, -1, vals[0].first, vals[1].first, vals[2].first);
		if(ans.first >= 0) 
		{
			//cerr << ans.first << " " << ans.second << '\n';
			int num = vals[0].first;
			set_ans(ans.first, ans.second, vals[0].second, num);
			num = vals[1].first;
			set_ans(ans.second, ans.first, vals[1].second, num);

			for(int i = 0; i < n; i ++)
			{
				if(res[i] == 0) res[i] = vals[2].second;
			}
		}

	}
	
	return res;
}

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