oj.uz

Submission #145408

# Submission time Handle Problem Language Result Execution time Memory
145408 2019-08-19T19:42:44 Z Eae02 Split the Attractions (IOI19_split) C++14
7 / 100
 95 ms 14968 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] = 0;
	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] = 1;
	
	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 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 380 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 3 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 91 ms 14968 KB ok, correct split
8 Correct 95 ms 13432 KB ok, correct split
9 Correct 82 ms 13056 KB ok, correct split
10 Correct 81 ms 14760 KB ok, correct split
11 Correct 86 ms 14112 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 376 KB Execution failed because the return code was nonzero
4 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 78 ms 9352 KB invalid split: #1=40000, #2=20000, #3=40000
3 Halted 0 ms 0 KB -

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 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 380 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 3 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 91 ms 14968 KB ok, correct split
8 Correct 95 ms 13432 KB ok, correct split
9 Correct 82 ms 13056 KB ok, correct split
10 Correct 81 ms 14760 KB ok, correct split
11 Correct 86 ms 14112 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 376 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -