Submission #144011

#	Time	Username	Problem	Language	Result	Execution time	Memory
144011		tincamatei	Split the Attractions (IOI19_split)	C++14	29 / 100	923 ms	1048580 KiB

split

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

using namespace std;

const int MAX_N = 100000;
vector<int> graph[MAX_N];
vector<int> rez;

int target[3];
int color[3];
int subarb[MAX_N];

void colorNodes(int col, int nod, int papa) {
	if(target[color[col]] > 0) {
		rez[nod] = color[col] + 1;
		target[color[col]]--;
	} else
		rez[nod] = color[2] + 1;
	
	for(auto it: graph[nod])
		if(it != papa)
			colorNodes(col, it, nod);
}

bool dfs(int N, int nod, int papa = -1) {
	subarb[nod] = 1;
	for(auto it: graph[nod]) {
		if(it != papa) {
			bool rez = dfs(N, it, nod);
			
			if(rez == true)
				return true;

			subarb[nod] += subarb[it];

			if(subarb[it] >= target[color[0]] && N - subarb[it] >= target[color[1]]) {
				colorNodes(0, it, nod);
				colorNodes(1, nod, it);
				return true;
			} else if(subarb[it] >= target[color[1]] && N - subarb[it] >= target[color[0]]){
				colorNodes(1, it, nod);
				colorNodes(0, nod, it);
				return true;
			}
		}
	}

	return false;
}

bool cmp(int a, int b) {
	return target[a] < target[b];
}

vector<int> subtask3(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	int M = p.size();
	rez = vector<int>(N, 0);
	for(int i = 0; i < N - 1; ++i) {
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	target[0] = a;
	target[1] = b;
	target[2] = c;
	for(int i = 0; i < 3; ++i)
		color[i] = i;

	sort(color, color + 3, cmp);
	
	dfs(N, 0);

	return rez;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	return subtask3(N, a, b, c, p, q);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> subtask3(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:58:6: warning: unused variable 'M' [-Wunused-variable]
  int M = p.size();
      ^

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