oj.uz

Submission #170766

# Submission time Handle Problem Language Result Execution time Memory
170766 2019-12-26T09:59:52 Z Sorting Split the Attractions (IOI19_split) C++14
40 / 100
 129 ms 19632 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;

const int MAXN = 2e5 + 7;

int n, a, b, c;
int num_a, num_b, num_c;
vector<int> p, q;
vector<int> adj[MAXN];
bool used[MAXN];
int sz[MAXN], par[MAXN];
vector<int> ans;

int dfs(int u){
	if(u == 0)
		par[u] = -1;

	used[u] = true;
	sz[u] = 1;

	int ret = -1;
	for(int to: adj[u]){
		if(used[to])
			continue;

		par[to] = u;
		int curr = dfs(to);
		sz[u] += sz[to];

		if(ret == -1)
			ret = curr;
	}

	if(ret == -1 && sz[u] >= a)
		ret = u;

	return ret;
}

int dfs_fill(int u, int nodes, int color){
	if(!nodes)
		return 0;

	used[u] = true;
	--nodes;
	ans[u] = color;

	for(int to: adj[u]){
		if(used[to])
			continue;

		nodes = dfs_fill(to, nodes, color);
	}

	return nodes;
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q) {
	n = _n, a = _a, b = _b, c = _c, p = _p, q = _q;
	num_a = 1;
	num_b = 2;
	num_c = 3;

	if(a > b){
		swap(a, b);
		swap(num_a, num_b);
	}
	if(a > c){
		swap(a, c);
		swap(num_a, num_c);
	}
	if(b > c){
		swap(b, c);
		swap(num_b, num_c);
	}
	ans.resize(n, 0);

	for(int i = 0; i < (int)p.size(); ++i){
		int u = p[i], v = q[i];

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int u = dfs(0);

	if(n - sz[u] < a)
		return vector<int>(n, 0);

	for(int i = 0; i < n; ++i)
		used[i] = false;

	if(n - sz[u] > sz[u]){
		used[u] = true;
		dfs_fill(par[u], b, num_b);
		used[u] = false;
		used[par[u]] = true;
		dfs_fill(u, a, num_a);
	}
	else{
		used[u] = true;
		dfs_fill(par[u], a, num_a);
		used[u] = false;
		used[par[u]] = true;
		dfs_fill(u, b, num_b);
	}

	for(int &val: ans){
		if(val == 0)
			val = num_c;
	}

	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 5036 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 5004 KB ok, correct split
7 Correct 95 ms 19272 KB ok, correct split
8 Correct 92 ms 17524 KB ok, correct split
9 Correct 88 ms 16888 KB ok, correct split
10 Correct 95 ms 19548 KB ok, correct split
11 Correct 104 ms 19616 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4956 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 119 ms 18328 KB ok, correct split
5 Correct 116 ms 13480 KB ok, correct split
6 Correct 103 ms 19632 KB ok, correct split
7 Correct 109 ms 17368 KB ok, correct split
8 Correct 129 ms 17468 KB ok, correct split
9 Correct 87 ms 13436 KB ok, correct split
10 Correct 67 ms 13296 KB ok, correct split
11 Correct 68 ms 13364 KB ok, correct split
12 Correct 68 ms 13772 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 83 ms 13360 KB ok, correct split
3 Correct 34 ms 8416 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 90 ms 15452 KB ok, correct split
6 Correct 86 ms 15200 KB ok, correct split
7 Correct 85 ms 15056 KB ok, correct split
8 Correct 88 ms 16160 KB ok, correct split
9 Correct 88 ms 14988 KB ok, correct split
10 Correct 29 ms 7772 KB ok, no valid answer
11 Correct 43 ms 9208 KB ok, no valid answer
12 Correct 73 ms 13656 KB ok, no valid answer
13 Correct 81 ms 13452 KB ok, no valid answer
14 Correct 69 ms 13776 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, no valid answer
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 7 ms 4984 KB ok, correct split
7 Incorrect 6 ms 4956 KB invalid split: #1=3, #2=4, #3=5
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 5036 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 5004 KB ok, correct split
7 Correct 95 ms 19272 KB ok, correct split
8 Correct 92 ms 17524 KB ok, correct split
9 Correct 88 ms 16888 KB ok, correct split
10 Correct 95 ms 19548 KB ok, correct split
11 Correct 104 ms 19616 KB ok, correct split
12 Correct 6 ms 4956 KB ok, correct split
13 Correct 6 ms 4984 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 119 ms 18328 KB ok, correct split
16 Correct 116 ms 13480 KB ok, correct split
17 Correct 103 ms 19632 KB ok, correct split
18 Correct 109 ms 17368 KB ok, correct split
19 Correct 129 ms 17468 KB ok, correct split
20 Correct 87 ms 13436 KB ok, correct split
21 Correct 67 ms 13296 KB ok, correct split
22 Correct 68 ms 13364 KB ok, correct split
23 Correct 68 ms 13772 KB ok, correct split
24 Correct 6 ms 4984 KB ok, correct split
25 Correct 83 ms 13360 KB ok, correct split
26 Correct 34 ms 8416 KB ok, correct split
27 Correct 6 ms 4984 KB ok, correct split
28 Correct 90 ms 15452 KB ok, correct split
29 Correct 86 ms 15200 KB ok, correct split
30 Correct 85 ms 15056 KB ok, correct split
31 Correct 88 ms 16160 KB ok, correct split
32 Correct 88 ms 14988 KB ok, correct split
33 Correct 29 ms 7772 KB ok, no valid answer
34 Correct 43 ms 9208 KB ok, no valid answer
35 Correct 73 ms 13656 KB ok, no valid answer
36 Correct 81 ms 13452 KB ok, no valid answer
37 Correct 69 ms 13776 KB ok, no valid answer
38 Correct 6 ms 4984 KB ok, correct split
39 Correct 6 ms 4984 KB ok, no valid answer
40 Correct 6 ms 4984 KB ok, correct split
41 Correct 6 ms 4984 KB ok, correct split
42 Correct 6 ms 4984 KB ok, correct split
43 Correct 7 ms 4984 KB ok, correct split
44 Incorrect 6 ms 4956 KB invalid split: #1=3, #2=4, #3=5
45 Halted 0 ms 0 KB -