oj.uz

Submission #145393

# Submission time Handle Problem Language Result Execution time Memory
145393 2019-08-19T19:29:32 Z Eae02 Split the Attractions (IOI19_split) C++14
0 / 100
 75 ms 9292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 2 ms 376 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 2 ms 256 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 75 ms 9292 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 2 ms 376 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -