oj.uz

Submission #145411

# Submission time Handle Problem Language Result Execution time Memory
145411 2019-08-19T19:46:07 Z Eae02 Split the Attractions (IOI19_split) C++14
33 / 100
 982 ms 1048580 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);
	
	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 || numEdges == numNodes) {
		if (numEdges == numNodes) {
			edges1.pop_back();
			edges2.pop_back();
			numEdges--;
		}
		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
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 256 KB ok, correct split
4 Runtime error 982 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

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 256 KB ok, correct split
4 Correct 91 ms 11216 KB ok, correct split
5 Correct 74 ms 9728 KB ok, correct split
6 Correct 75 ms 9556 KB ok, correct split
7 Correct 74 ms 11044 KB ok, correct split
8 Correct 126 ms 11472 KB ok, correct split
9 Correct 71 ms 8444 KB ok, correct split
10 Correct 60 ms 8744 KB ok, correct split
11 Correct 58 ms 8944 KB ok, correct split
12 Correct 59 ms 8744 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 76 ms 9256 KB ok, correct split
3 Correct 29 ms 3920 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 84 ms 10744 KB ok, correct split
6 Correct 79 ms 10552 KB ok, correct split
7 Correct 110 ms 10448 KB ok, correct split
8 Correct 83 ms 11256 KB ok, correct split
9 Correct 86 ms 10360 KB ok, correct split
10 Correct 24 ms 3320 KB ok, no valid answer
11 Correct 35 ms 4728 KB ok, no valid answer
12 Correct 65 ms 9460 KB ok, no valid answer
13 Correct 77 ms 9336 KB ok, no valid answer
14 Correct 71 ms 9584 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 256 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 256 KB ok, correct split
4 Runtime error 982 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -