Submission #145393

#	Time	Username	Problem	Language	Result	Execution time	Memory
145393		Eae02	Split the Attractions (IOI19_split)	C++14	0 / 100	75 ms	9292 KiB

split

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

using namespace std;

int numNodes;
vector<int> ans;
vector<int> edges1;
vector<int> edges2;

vector<vector<int>> neigh;

vector<int> par;
vector<int> stSize;

void initTree(int n, int p) {
	par[n] = p;
	stSize[n] = 1;
	for (int i = 0; i < (int)neigh[n].size(); i++) {
		if (neigh[n][i] != p) {
			initTree(neigh[n][i], n);
			stSize[n] += stSize[neigh[n][i]];
		}
	}
}

int remA, remB;

vector<bool> fillVis;

void fillA(int n) {
	if (remA == 0)
		return;
	
	remA--;
	ans[n] = 0;
	fillVis[n] = true;
	
	for (int c : neigh[n]) {
		if (c != par[n]) {
			fillA(c);
		}
	}
}

void fillB(int n) {
	if (remB == 0 || fillVis[n])
		return;
	
	fillVis[n] = true;
	remB--;
	ans[n] = 1;
	
	for (int c : neigh[n]) {
		fillB(c);
	}
}

bool solveTree(int a, int b, int c) {
	stSize.resize(numNodes);
	par.resize(numNodes);
	fillVis.resize(numNodes);
	initTree(0, -1);
	
	int aRoot = -1;
	for (int i = 0; i < numNodes; i++) {
		int numUp = numNodes - stSize[i];
		if (stSize[i] >= a && numUp >= b) {
			aRoot = i;
			break;
		}
	}
	
	if (aRoot == -1)
		return false;
	
	fill(ans.begin(), ans.end(), 2);
	
	remA = a;
	remB = b;
	fillA(aRoot);
	fillB(par[aRoot]);
	
	return true;
}

vector<int> find_split(int _numNodes, int a, int b, int c, vector<int> p, vector<int> q) {
	edges1 = move(p);
	edges2 = move(q);
	
	numNodes = _numNodes;
	ans.resize(numNodes);
	
	neigh.resize(numNodes);
	for (int i = 0; i < (int)edges1.size(); i++) {
		neigh[edges1[i]].push_back(edges2[i]);
		neigh[edges2[i]].push_back(edges1[i]);
	}
	
	pair<int, int> abc[] = { { a, 1 }, { b, 2 }, { c, 3 } };
	sort(abc, abc + 3);
	
	int numEdges = (int)edges1.size();
	bool can = false;
	if (numEdges == numNodes - 1) {
		can = solveTree(abc[0].first, abc[1].first, abc[2].first);
	}
	
	if (!can) {
		fill(ans.begin(), ans.end(), 0);
	} else {
		for (int& i : ans) {
			i = abc[i].second;
		}
	}
	
	return ans;
}

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