Submission #1290978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290978		gustavo_d	Split the Attractions (IOI19_split)	C++20	7 / 100	607 ms	1114112 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

pair<int, int> target[3];
vector<int> adj[MAXN];
vector<int> res;
int subSz[MAXN]; int n;

int dfs2(int v, int pai, int get, int c) {
	if (get <= 0) return 0;
	res[v] = c;
	int got = 1;
	for (int viz : adj[v]) {
		if (viz == pai) continue;
		got += dfs2(viz, v, get - got, c);
	}
	return got;
}

bool dfs(int v, int pai) {
	// cerr <<  v << endl;
	subSz[v] = 1;
	for (int viz : adj[v]) {
		if (viz == pai) continue;
		if (dfs(viz, v)) return true;
		subSz[v] += subSz[viz];
	}

	if (pai == 1) return false;

	if (subSz[v] >= target[0].first and n - subSz[v] >= target[0].first) {
		dfs2(v, pai, target[0].first, target[0].second);
		dfs2(pai, v, target[1].first, target[1].second);
		return true;
	}

	return false;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;

	for (int i=0; i<n-1; i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	target[0] = make_pair(a, 1);
	target[1] = make_pair(b, 2);
	target[2] = make_pair(c, 3);
	sort(target, target+3);
	
	res = vector<int> (n, -1);

	if (!dfs(0, -1))
		res = vector<int> (n, 0);
	else {
		for (int i=0; i<n; i++) {
			if (res[i] == -1) res[i] = target[2].second;
		}
	}

	return res;
}

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