oj.uz

Submission #167782

# Submission time Handle Problem Language Result Execution time Memory
167782 2019-12-10T06:29:31 Z oolimry Split the Attractions (IOI19_split) C++14
18 / 100
 174 ms 25848 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;

static vi answer;
static vi adj[100005];
static vi child[100005];
static vi tree[100005];
static int sz[100005];
static int p[100005];
static bool vis[100005];

void dfs(int u){
	vis[u] = true;
	sz[u] = 1;
	for(int v : adj[u]){
		if(!vis[v]){
			child[u].push_back(v);
			tree[u].push_back(v);
			tree[v].push_back(u);
			p[v] = u;
			dfs(v);
			sz[u] += sz[v];
		}	
	}
}

void bfs(int root, int number){
	if(number == 0) return;
	queue<int> bf;
	bf.push(root);
	while(!bf.empty()){
		int u = bf.front(); bf.pop();
		for(int v : tree[u]){
			if(answer[v] == 0){
				answer[v] = answer[u];
				number--;
				if(number == 0) return;
				bf.push(v);
			}
		}
	}
}
vi find_split(int n, int aaa, int bbb, int ccc, vi p, vi q) {
	vector<ii> v = {ii(aaa,1),ii(bbb,2),ii(ccc,3)};
	sort(v.begin(),v.end());
	int A = v[0].first;
	int B = v[1].first;
	int AColour = v[0].second;
	int BColour = v[1].second;
	int CColour = v[2].second;
	
	answer.assign(n,0);
	
	for(int i = 0;i < (int) p.size();i++){
		int x = p[i], y = q[i];
		adj[y].push_back(x);
		adj[x].push_back(y);
	}
	
	dfs(0);
	
	for(int u = 0;u < n;u++){
		vector<ii> subtrees;
		for(int v : child[u]){
			subtrees.push_back({sz[v],v});
		}
		subtrees.push_back({n - sz[u],p[u]});
		
		for(ii x : subtrees){
			if(x.first >= A && n - x.first >= B){
				//cout << x.second << " " << u << "\n";
				answer[x.second] = AColour;
				answer[u] = BColour;
				bfs(x.second, A-1);
				bfs(u,B-1);
				for(int i = 0;i < n;i++){
					if(answer[i] == 0) answer[i] = CColour;
				}
				return answer;
			}
		}
	}
	
	return answer;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7288 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 139 ms 25592 KB ok, correct split
8 Correct 140 ms 23800 KB ok, correct split
9 Correct 151 ms 23180 KB ok, correct split
10 Correct 142 ms 25848 KB ok, correct split
11 Correct 150 ms 25796 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 10 ms 7416 KB ok, correct split
4 Correct 153 ms 22620 KB ok, correct split
5 Correct 120 ms 18424 KB ok, correct split
6 Correct 137 ms 25848 KB ok, correct split
7 Correct 151 ms 23544 KB ok, correct split
8 Correct 174 ms 20984 KB ok, correct split
9 Correct 133 ms 19704 KB ok, correct split
10 Correct 86 ms 18416 KB ok, correct split
11 Correct 86 ms 18416 KB ok, correct split
12 Correct 93 ms 18416 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Incorrect 134 ms 18296 KB invalid split: #1=9274, #2=40000, #3=50726
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7420 KB ok, correct split
2 Correct 8 ms 7416 KB ok, no valid answer
3 Correct 10 ms 7308 KB ok, correct split
4 Correct 10 ms 7288 KB ok, correct split
5 Correct 9 ms 7416 KB ok, correct split
6 Correct 9 ms 7416 KB ok, correct split
7 Correct 8 ms 7416 KB ok, correct split
8 Correct 8 ms 7416 KB ok, correct split
9 Correct 13 ms 7672 KB ok, correct split
10 Correct 13 ms 7672 KB ok, correct split
11 Correct 10 ms 7416 KB ok, correct split
12 Correct 13 ms 7676 KB ok, correct split
13 Correct 9 ms 7416 KB ok, correct split
14 Correct 9 ms 7416 KB ok, correct split
15 Correct 9 ms 7416 KB ok, correct split
16 Correct 9 ms 7416 KB ok, correct split
17 Correct 8 ms 7416 KB ok, correct split
18 Correct 8 ms 7420 KB ok, correct split
19 Correct 8 ms 7416 KB ok, correct split
20 Correct 9 ms 7544 KB ok, correct split
21 Correct 10 ms 7672 KB ok, correct split
22 Incorrect 10 ms 7672 KB invalid split: #1=424, #2=850, #3=1226
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7288 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 139 ms 25592 KB ok, correct split
8 Correct 140 ms 23800 KB ok, correct split
9 Correct 151 ms 23180 KB ok, correct split
10 Correct 142 ms 25848 KB ok, correct split
11 Correct 150 ms 25796 KB ok, correct split
12 Correct 8 ms 7416 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 10 ms 7416 KB ok, correct split
15 Correct 153 ms 22620 KB ok, correct split
16 Correct 120 ms 18424 KB ok, correct split
17 Correct 137 ms 25848 KB ok, correct split
18 Correct 151 ms 23544 KB ok, correct split
19 Correct 174 ms 20984 KB ok, correct split
20 Correct 133 ms 19704 KB ok, correct split
21 Correct 86 ms 18416 KB ok, correct split
22 Correct 86 ms 18416 KB ok, correct split
23 Correct 93 ms 18416 KB ok, correct split
24 Correct 8 ms 7416 KB ok, correct split
25 Incorrect 134 ms 18296 KB invalid split: #1=9274, #2=40000, #3=50726
26 Halted 0 ms 0 KB -