oj.uz

Submission #240878

# Submission time Handle Problem Language Result Execution time Memory
240878 2020-06-21T10:58:39 Z zoomswk Split the Attractions (IOI19_split) C++17
40 / 100
 137 ms 15476 KB 
#include "split.h"
#include <vector>
#include <algorithm>
using namespace std;

vector<int> way[100005];
int par[100005];
int sz[100005];

int dfs(int node, int p=-1){
	if(sz[node] > 0) return 0;
	par[node] = p;
	sz[node] = 1;
	for(int x : way[node]) sz[node] += dfs(x, node);
	return sz[node];
}

int is_in[100005];
vector<int> whats_in;
vector<int> whats_in2;

void go(int node){
	is_in[node] = 1;
	whats_in.push_back(node);
	for(int x : way[node]) if(par[x] == node) go(x);
	return;
}

void go2(int node){
	if(is_in[node]) return;
	whats_in2.push_back(node);
	for(int x : way[node]) if(par[x] == node) go2(x);
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = (int)p.size();
	for(int i=0; i<m; i++){
		way[p[i]].push_back(q[i]);
		way[q[i]].push_back(p[i]);
	}
	dfs(0);
	vector<pair<int, int>> vv = {{a, 1}, {b, 2}, {c, 3}};
	sort(vv.begin(), vv.end());
	vector<int> res(n, 0);
	for(int i=0; i<n; i++){
		if(sz[i] >= vv[0].first && n-sz[i] >= vv[1].first){
			go(i);
			go2(0);
			for(int j=0; j<whats_in.size(); j++){
				if(j < vv[0].first) res[whats_in[j]] = vv[0].second;
				else res[whats_in[j]] = vv[2].second;
			}
			for(int j=0; j<whats_in2.size(); j++){
				if(j < vv[1].first) res[whats_in2[j]] = vv[1].second;
				else res[whats_in2[j]] = vv[2].second;
			}
			return res;
		} else if(sz[i] >= vv[1].first && n-sz[i] >= vv[0].first){
			go(i);
			go2(0);
			for(int j=0; j<whats_in.size(); j++){
				if(j < vv[1].first) res[whats_in[j]] = vv[1].second;
				else res[whats_in[j]] = vv[2].second;
			}
			for(int j=0; j<whats_in2.size(); j++){
				if(j < vv[0].first) res[whats_in2[j]] = vv[0].second;
				else res[whats_in2[j]] = vv[2].second;
			}
			return res;
		}
	}
	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in2.size(); j++){
                 ~^~~~~~~~~~~~~~~~~
split.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in2.size(); j++){
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 111 ms 14072 KB ok, correct split
8 Correct 100 ms 12664 KB ok, correct split
9 Correct 123 ms 12288 KB ok, correct split
10 Correct 112 ms 14324 KB ok, correct split
11 Correct 105 ms 14200 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 126 ms 12916 KB ok, correct split
5 Correct 107 ms 10488 KB ok, correct split
6 Correct 99 ms 15476 KB ok, correct split
7 Correct 132 ms 13812 KB ok, correct split
8 Correct 137 ms 13688 KB ok, correct split
9 Correct 98 ms 10616 KB ok, correct split
10 Correct 60 ms 10608 KB ok, correct split
11 Correct 61 ms 10860 KB ok, correct split
12 Correct 59 ms 10864 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 96 ms 9724 KB ok, correct split
3 Correct 32 ms 5632 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 101 ms 11252 KB ok, correct split
6 Correct 96 ms 11124 KB ok, correct split
7 Correct 99 ms 10872 KB ok, correct split
8 Correct 95 ms 11768 KB ok, correct split
9 Correct 98 ms 10744 KB ok, correct split
10 Correct 31 ms 4608 KB ok, no valid answer
11 Correct 34 ms 5632 KB ok, no valid answer
12 Correct 73 ms 8820 KB ok, no valid answer
13 Correct 69 ms 8696 KB ok, no valid answer
14 Correct 57 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, no valid answer
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 6 ms 2688 KB ok, correct split
8 Correct 6 ms 2688 KB ok, correct split
9 Correct 8 ms 2944 KB ok, correct split
10 Correct 8 ms 2944 KB ok, correct split
11 Correct 6 ms 2688 KB ok, correct split
12 Correct 9 ms 2944 KB ok, correct split
13 Correct 6 ms 2688 KB ok, correct split
14 Correct 6 ms 2688 KB ok, correct split
15 Correct 6 ms 2688 KB ok, correct split
16 Correct 6 ms 2688 KB ok, correct split
17 Correct 6 ms 2688 KB ok, correct split
18 Correct 6 ms 2688 KB ok, correct split
19 Correct 7 ms 2688 KB ok, correct split
20 Correct 7 ms 2816 KB ok, correct split
21 Correct 7 ms 2944 KB ok, correct split
22 Correct 7 ms 2944 KB ok, correct split
23 Correct 7 ms 2944 KB ok, correct split
24 Correct 8 ms 2944 KB ok, correct split
25 Correct 8 ms 2944 KB ok, correct split
26 Incorrect 8 ms 2944 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 111 ms 14072 KB ok, correct split
8 Correct 100 ms 12664 KB ok, correct split
9 Correct 123 ms 12288 KB ok, correct split
10 Correct 112 ms 14324 KB ok, correct split
11 Correct 105 ms 14200 KB ok, correct split
12 Correct 6 ms 2688 KB ok, correct split
13 Correct 6 ms 2688 KB ok, correct split
14 Correct 6 ms 2688 KB ok, correct split
15 Correct 126 ms 12916 KB ok, correct split
16 Correct 107 ms 10488 KB ok, correct split
17 Correct 99 ms 15476 KB ok, correct split
18 Correct 132 ms 13812 KB ok, correct split
19 Correct 137 ms 13688 KB ok, correct split
20 Correct 98 ms 10616 KB ok, correct split
21 Correct 60 ms 10608 KB ok, correct split
22 Correct 61 ms 10860 KB ok, correct split
23 Correct 59 ms 10864 KB ok, correct split
24 Correct 6 ms 2688 KB ok, correct split
25 Correct 96 ms 9724 KB ok, correct split
26 Correct 32 ms 5632 KB ok, correct split
27 Correct 6 ms 2688 KB ok, correct split
28 Correct 101 ms 11252 KB ok, correct split
29 Correct 96 ms 11124 KB ok, correct split
30 Correct 99 ms 10872 KB ok, correct split
31 Correct 95 ms 11768 KB ok, correct split
32 Correct 98 ms 10744 KB ok, correct split
33 Correct 31 ms 4608 KB ok, no valid answer
34 Correct 34 ms 5632 KB ok, no valid answer
35 Correct 73 ms 8820 KB ok, no valid answer
36 Correct 69 ms 8696 KB ok, no valid answer
37 Correct 57 ms 8944 KB ok, no valid answer
38 Correct 6 ms 2688 KB ok, correct split
39 Correct 6 ms 2688 KB ok, no valid answer
40 Correct 6 ms 2688 KB ok, correct split
41 Correct 6 ms 2688 KB ok, correct split
42 Correct 6 ms 2688 KB ok, correct split
43 Correct 6 ms 2688 KB ok, correct split
44 Correct 6 ms 2688 KB ok, correct split
45 Correct 6 ms 2688 KB ok, correct split
46 Correct 8 ms 2944 KB ok, correct split
47 Correct 8 ms 2944 KB ok, correct split
48 Correct 6 ms 2688 KB ok, correct split
49 Correct 9 ms 2944 KB ok, correct split
50 Correct 6 ms 2688 KB ok, correct split
51 Correct 6 ms 2688 KB ok, correct split
52 Correct 6 ms 2688 KB ok, correct split
53 Correct 6 ms 2688 KB ok, correct split
54 Correct 6 ms 2688 KB ok, correct split
55 Correct 6 ms 2688 KB ok, correct split
56 Correct 7 ms 2688 KB ok, correct split
57 Correct 7 ms 2816 KB ok, correct split
58 Correct 7 ms 2944 KB ok, correct split
59 Correct 7 ms 2944 KB ok, correct split
60 Correct 7 ms 2944 KB ok, correct split
61 Correct 8 ms 2944 KB ok, correct split
62 Correct 8 ms 2944 KB ok, correct split
63 Incorrect 8 ms 2944 KB jury found a solution, contestant did not
64 Halted 0 ms 0 KB -