oj.uz

Submission #144007

# Submission time Handle Problem Language Result Execution time Memory
144007 2019-08-15T16:13:41 Z tincamatei Split the Attractions (IOI19_split) C++14
22 / 100
 110 ms 12792 KB 
#include "split.h"
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAX_N = 100000;
vector<int> graph[MAX_N];
vector<int> rez;

int target[3];
int color[3];
int subarb[MAX_N];

void colorNodes(int col, int nod, int papa) {
	if(target[color[col]] > 0) {
		rez[nod] = color[col] + 1;
		target[color[col]]--;
	} else
		rez[nod] = color[2] + 1;
	
	for(auto it: graph[nod])
		if(it != papa)
			colorNodes(col, it, nod);
}

bool dfs(int N, int nod, int papa = -1) {
	subarb[nod] = 1;
	for(auto it: graph[nod]) {
		if(it != papa) {
			bool rez = dfs(N, it, nod);
			
			if(rez == true)
				return true;

			subarb[nod] += subarb[it];

			if(subarb[it] >= target[color[0]] && N - subarb[it] >= target[color[1]]) {
				colorNodes(0, it, nod);
				colorNodes(1, nod, it);
				return true;
			} else if(subarb[it] >= target[color[1]] && N - subarb[it] >= target[color[0]]){
				colorNodes(1, it, nod);
				colorNodes(0, nod, it);
				return true;
			}
		}
	}

	return false;
}

bool cmp(int a, int b) {
	return target[a] < target[b];
}

vector<int> subtask3(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	int M = p.size();
	rez = vector<int>(N, 0);
	for(int i = 0; i < M; ++i) {
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	target[0] = a;
	target[1] = b;
	target[2] = c;
	for(int i = 0; i < 3; ++i)
		color[i] = i;

	sort(color, color + 3, cmp);
	
	dfs(N, 0);

	return rez;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	int M = p.size();
	if(M == N - 1)
		return subtask3(N, a, b, c, p, q);
	return rez;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Incorrect 4 ms 2680 KB WA in grader: Invalid length of the result.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Incorrect 4 ms 2680 KB WA in grader: Invalid length of the result.
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 87 ms 9464 KB ok, correct split
3 Correct 31 ms 5368 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 91 ms 11900 KB ok, correct split
6 Correct 90 ms 11712 KB ok, correct split
7 Correct 100 ms 11512 KB ok, correct split
8 Correct 105 ms 12792 KB ok, correct split
9 Correct 110 ms 11384 KB ok, correct split
10 Correct 26 ms 4856 KB ok, no valid answer
11 Correct 38 ms 6008 KB ok, no valid answer
12 Correct 73 ms 9588 KB ok, no valid answer
13 Correct 77 ms 9592 KB ok, no valid answer
14 Correct 63 ms 9624 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Incorrect 4 ms 2680 KB WA in grader: Invalid length of the result.
3 Halted 0 ms 0 KB -