oj.uz

Submission #145413

# Submission time Handle Problem Language Result Execution time Memory
145413 2019-08-19T19:47:09 Z Eae02 Split the Attractions (IOI19_split) C++14
40 / 100
 116 ms 14712 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 remFill;

vector<bool> fillVis;

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

void fill(int n, int v) {
	if (remFill == 0 || fillVis[n])
		return;
	
	fillVis[n] = true;
	remFill--;
	ans[n] = v;
	
	for (int c : neigh[n]) {
		fill(c, v);
	}
}

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

bool solveA1(int a, int b, int c) {
	fill(ans.begin(), ans.end(), 2);
	
	remFill = b;
	fill(0, 1);
	
	for (int& i : ans) {
		if (i == 2) {
			i = 0;
			break;
		}
	}
	
	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);
	
	int numEdges = (int)edges1.size();
	
	fillVis.resize(numNodes, false);
	
	if (numEdges == numNodes && a != 1) {
		edges1.pop_back();
		edges2.pop_back();
		numEdges--;
	}
	
	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);
	
	bool can = false;
	if (a == 1) {
		can = solveA1(abc[0].first, abc[1].first, abc[2].first);
	} else if (numEdges == numNodes - 1) {
		
		can = solveTree(abc[0].first, abc[1].first, abc[2].first);
	} else {
		exit(1);
	}
	
	if (!can) {
		fill(ans.begin(), ans.end(), 0);
	} else {
		for (int& i : ans) {
			i = abc[i].second;
		}
	}
	
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 5 ms 256 KB ok, correct split
5 Correct 2 ms 256 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 101 ms 14712 KB ok, correct split
8 Correct 69 ms 9464 KB ok, correct split
9 Correct 101 ms 13044 KB ok, correct split
10 Correct 83 ms 9496 KB ok, correct split
11 Correct 94 ms 14200 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 93 ms 11256 KB ok, correct split
5 Correct 72 ms 9592 KB ok, correct split
6 Correct 71 ms 9456 KB ok, correct split
7 Correct 74 ms 11128 KB ok, correct split
8 Correct 116 ms 11360 KB ok, correct split
9 Correct 77 ms 8404 KB ok, correct split
10 Correct 58 ms 8688 KB ok, correct split
11 Correct 66 ms 8816 KB ok, correct split
12 Correct 62 ms 8732 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 80 ms 9252 KB ok, correct split
3 Correct 29 ms 3960 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 88 ms 10744 KB ok, correct split
6 Correct 100 ms 10588 KB ok, correct split
7 Correct 84 ms 10540 KB ok, correct split
8 Correct 87 ms 11384 KB ok, correct split
9 Correct 104 ms 10336 KB ok, correct split
10 Correct 24 ms 3324 KB ok, no valid answer
11 Correct 36 ms 4728 KB ok, no valid answer
12 Correct 66 ms 9460 KB ok, no valid answer
13 Correct 77 ms 9308 KB ok, no valid answer
14 Correct 63 ms 9584 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 5 ms 256 KB ok, correct split
5 Correct 2 ms 256 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 101 ms 14712 KB ok, correct split
8 Correct 69 ms 9464 KB ok, correct split
9 Correct 101 ms 13044 KB ok, correct split
10 Correct 83 ms 9496 KB ok, correct split
11 Correct 94 ms 14200 KB ok, correct split
12 Correct 2 ms 256 KB ok, correct split
13 Correct 2 ms 256 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 93 ms 11256 KB ok, correct split
16 Correct 72 ms 9592 KB ok, correct split
17 Correct 71 ms 9456 KB ok, correct split
18 Correct 74 ms 11128 KB ok, correct split
19 Correct 116 ms 11360 KB ok, correct split
20 Correct 77 ms 8404 KB ok, correct split
21 Correct 58 ms 8688 KB ok, correct split
22 Correct 66 ms 8816 KB ok, correct split
23 Correct 62 ms 8732 KB ok, correct split
24 Correct 2 ms 256 KB ok, correct split
25 Correct 80 ms 9252 KB ok, correct split
26 Correct 29 ms 3960 KB ok, correct split
27 Correct 2 ms 376 KB ok, correct split
28 Correct 88 ms 10744 KB ok, correct split
29 Correct 100 ms 10588 KB ok, correct split
30 Correct 84 ms 10540 KB ok, correct split
31 Correct 87 ms 11384 KB ok, correct split
32 Correct 104 ms 10336 KB ok, correct split
33 Correct 24 ms 3324 KB ok, no valid answer
34 Correct 36 ms 4728 KB ok, no valid answer
35 Correct 66 ms 9460 KB ok, no valid answer
36 Correct 77 ms 9308 KB ok, no valid answer
37 Correct 63 ms 9584 KB ok, no valid answer
38 Runtime error 2 ms 376 KB Execution failed because the return code was nonzero
39 Halted 0 ms 0 KB -