oj.uz

Submission #145409

# Submission time Handle Problem Language Result Execution time Memory
145409 2019-08-19T19:43:16 Z Eae02 Split the Attractions (IOI19_split) C++14
29 / 100
 100 ms 14828 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);
	fillVis.resize(numNodes, false);
	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;
}

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();
	if (numEdges == numNodes) {
		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 (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 348 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 256 KB ok, correct split
4 Correct 2 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 86 ms 14828 KB ok, correct split
8 Correct 78 ms 13432 KB ok, correct split
9 Correct 86 ms 12364 KB ok, correct split
10 Correct 85 ms 14200 KB ok, correct split
11 Correct 89 ms 13432 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Runtime error 2 ms 256 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 90 ms 9336 KB ok, correct split
3 Correct 30 ms 3960 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 81 ms 10748 KB ok, correct split
6 Correct 82 ms 10488 KB ok, correct split
7 Correct 81 ms 10488 KB ok, correct split
8 Correct 83 ms 11256 KB ok, correct split
9 Correct 100 ms 10360 KB ok, correct split
10 Correct 25 ms 3320 KB ok, no valid answer
11 Correct 35 ms 4860 KB ok, no valid answer
12 Correct 69 ms 9468 KB ok, no valid answer
13 Correct 76 ms 9432 KB ok, no valid answer
14 Correct 64 ms 9600 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 348 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 348 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 256 KB ok, correct split
4 Correct 2 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 86 ms 14828 KB ok, correct split
8 Correct 78 ms 13432 KB ok, correct split
9 Correct 86 ms 12364 KB ok, correct split
10 Correct 85 ms 14200 KB ok, correct split
11 Correct 89 ms 13432 KB ok, correct split
12 Correct 2 ms 376 KB ok, correct split
13 Correct 2 ms 256 KB ok, correct split
14 Runtime error 2 ms 256 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -