oj.uz

Submission #167783

# Submission time Handle Problem Language Result Execution time Memory
167783 2019-12-10T06:30:50 Z oolimry Split the Attractions (IOI19_split) C++14
18 / 100
 179 ms 25868 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 : adj[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 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 9 ms 7416 KB ok, correct split
5 Correct 9 ms 7416 KB ok, correct split
6 Correct 10 ms 7420 KB ok, correct split
7 Correct 179 ms 25592 KB ok, correct split
8 Correct 136 ms 23800 KB ok, correct split
9 Correct 145 ms 23132 KB ok, correct split
10 Correct 138 ms 25868 KB ok, correct split
11 Correct 160 ms 25832 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 9 ms 7388 KB ok, correct split
4 Correct 161 ms 22564 KB ok, correct split
5 Correct 126 ms 18428 KB ok, correct split
6 Correct 134 ms 25848 KB ok, correct split
7 Correct 142 ms 23544 KB ok, correct split
8 Correct 170 ms 20984 KB ok, correct split
9 Correct 132 ms 19704 KB ok, correct split
10 Correct 90 ms 18416 KB ok, correct split
11 Correct 94 ms 18472 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 139 ms 18384 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 8 ms 7288 KB ok, correct split
2 Correct 10 ms 7420 KB ok, no valid answer
3 Correct 8 ms 7464 KB ok, correct split
4 Correct 10 ms 7288 KB ok, correct split
5 Correct 10 ms 7288 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 10 ms 7416 KB ok, correct split
8 Correct 8 ms 7416 KB ok, correct split
9 Correct 11 ms 7800 KB ok, correct split
10 Incorrect 11 ms 7672 KB invalid split: #1=33, #2=2466, #3=1
11 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 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 9 ms 7416 KB ok, correct split
5 Correct 9 ms 7416 KB ok, correct split
6 Correct 10 ms 7420 KB ok, correct split
7 Correct 179 ms 25592 KB ok, correct split
8 Correct 136 ms 23800 KB ok, correct split
9 Correct 145 ms 23132 KB ok, correct split
10 Correct 138 ms 25868 KB ok, correct split
11 Correct 160 ms 25832 KB ok, correct split
12 Correct 8 ms 7416 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 9 ms 7388 KB ok, correct split
15 Correct 161 ms 22564 KB ok, correct split
16 Correct 126 ms 18428 KB ok, correct split
17 Correct 134 ms 25848 KB ok, correct split
18 Correct 142 ms 23544 KB ok, correct split
19 Correct 170 ms 20984 KB ok, correct split
20 Correct 132 ms 19704 KB ok, correct split
21 Correct 90 ms 18416 KB ok, correct split
22 Correct 94 ms 18472 KB ok, correct split
23 Correct 93 ms 18416 KB ok, correct split
24 Correct 8 ms 7416 KB ok, correct split
25 Incorrect 139 ms 18384 KB invalid split: #1=9274, #2=40000, #3=50726
26 Halted 0 ms 0 KB -