oj.uz

Submission #167776

# Submission time Handle Problem Language Result Execution time Memory
167776 2019-12-10T06:12:54 Z oolimry Split the Attractions (IOI19_split) C++14
7 / 100
 186 ms 27128 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;
		if(u != 0) subtrees.push_back({n-1,p[u]});
		for(int v : child[u]){
			subtrees.push_back({sz[v],v});
			if(u != 0) subtrees[0].first -= sz[v];
		}
		
		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 7412 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 161 ms 26700 KB ok, correct split
8 Correct 145 ms 24952 KB ok, correct split
9 Correct 154 ms 24344 KB ok, correct split
10 Correct 151 ms 27128 KB ok, correct split
11 Correct 165 ms 27000 KB ok, correct split

Subtask #2
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 8 ms 7416 KB ok, correct split
4 Correct 158 ms 24428 KB ok, correct split
5 Correct 135 ms 19588 KB ok, correct split
6 Correct 149 ms 27000 KB ok, correct split
7 Correct 152 ms 24824 KB ok, correct split
8 Correct 186 ms 23032 KB ok, correct split
9 Correct 149 ms 20856 KB ok, correct split
10 Correct 93 ms 19184 KB ok, correct split
11 Incorrect 128 ms 19156 KB invalid split: #1=0, #2=49999, #3=50000
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Incorrect 140 ms 18368 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 9 ms 7416 KB ok, no valid answer
3 Correct 8 ms 7348 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7420 KB ok, correct split
6 Correct 8 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 7800 KB ok, correct split
10 Correct 12 ms 7800 KB ok, correct split
11 Correct 8 ms 7416 KB ok, correct split
12 Correct 11 ms 7800 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Incorrect 8 ms 7408 KB invalid split: #1=6, #2=4, #3=0
15 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 7412 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 161 ms 26700 KB ok, correct split
8 Correct 145 ms 24952 KB ok, correct split
9 Correct 154 ms 24344 KB ok, correct split
10 Correct 151 ms 27128 KB ok, correct split
11 Correct 165 ms 27000 KB ok, correct split
12 Correct 8 ms 7416 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 8 ms 7416 KB ok, correct split
15 Correct 158 ms 24428 KB ok, correct split
16 Correct 135 ms 19588 KB ok, correct split
17 Correct 149 ms 27000 KB ok, correct split
18 Correct 152 ms 24824 KB ok, correct split
19 Correct 186 ms 23032 KB ok, correct split
20 Correct 149 ms 20856 KB ok, correct split
21 Correct 93 ms 19184 KB ok, correct split
22 Incorrect 128 ms 19156 KB invalid split: #1=0, #2=49999, #3=50000
23 Halted 0 ms 0 KB -