oj.uz

Submission #240877

# Submission time Handle Problem Language Result Execution time Memory
240877 2020-06-21T10:56:02 Z zoomswk Split the Attractions (IOI19_split) C++17
29 / 100
 2000 ms 144856 KB 
#include "split.h"
#include <vector>
#include <algorithm>
using namespace std;

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

int dfs(int node){
	if(sz[node] > 0) return 0;
	sz[node] = 1;
	for(int x : way[node]) sz[node] += dfs(x);
	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(sz[x] < sz[node]) go(x);
	return;
}

void go2(int node){
	if(is_in[node]) return;
	whats_in2.push_back(node);
	for(int x : way[node]) if(sz[x] < sz[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:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in2.size(); j++){
                 ~^~~~~~~~~~~~~~~~~
split.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:64: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 102 ms 13304 KB ok, correct split
8 Correct 102 ms 13296 KB ok, correct split
9 Correct 92 ms 12692 KB ok, correct split
10 Correct 99 ms 14576 KB ok, correct split
11 Correct 95 ms 13432 KB ok, correct split

Subtask #2
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 Execution timed out 2100 ms 144856 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 78 ms 10488 KB ok, correct split
3 Correct 34 ms 5888 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 118 ms 11892 KB ok, correct split
6 Correct 90 ms 11892 KB ok, correct split
7 Correct 92 ms 11256 KB ok, correct split
8 Correct 93 ms 12020 KB ok, correct split
9 Correct 120 ms 11312 KB ok, correct split
10 Correct 26 ms 4864 KB ok, no valid answer
11 Correct 37 ms 6016 KB ok, no valid answer
12 Correct 62 ms 9716 KB ok, no valid answer
13 Correct 70 ms 9464 KB ok, no valid answer
14 Correct 61 ms 9712 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 Incorrect 6 ms 2816 KB invalid split: #1=3, #2=3, #3=5
5 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 102 ms 13304 KB ok, correct split
8 Correct 102 ms 13296 KB ok, correct split
9 Correct 92 ms 12692 KB ok, correct split
10 Correct 99 ms 14576 KB ok, correct split
11 Correct 95 ms 13432 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 Execution timed out 2100 ms 144856 KB Time limit exceeded
16 Halted 0 ms 0 KB -