oj.uz

Submission #167792

# Submission time Handle Problem Language Result Execution time Memory
167792 2019-12-10T07:00:59 Z oolimry Split the Attractions (IOI19_split) C++14
11 / 100
 177 ms 27000 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;
			}
		}
	}
	*/
	
	for(int i = 0;i < (int) p.size();i++){
		int x = p[i], y = q[i];
		if(sz[y] < sz[x]) swap(x,y); ///x is child of y
		
		int l = sz[x], r = n - sz[x];
		if(l > r) swap(l,r), swap(x,y);
		
		answer[x] = AColour;
		answer[y] = BColour;
		bfs(x,A-1);
		bfs(y,B-1);
		for(int i = 0;i < n;i++){
			if(answer[i] == 0) answer[i] = CColour;
		}
		return answer;
	}
	
	return answer;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7544 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 Incorrect 153 ms 26744 KB invalid split: #1=62088, #2=4579, #3=33333
8 Halted 0 ms 0 KB -

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 8 ms 7416 KB ok, correct split
4 Correct 167 ms 24304 KB ok, correct split
5 Correct 117 ms 19448 KB ok, correct split
6 Correct 149 ms 27000 KB ok, correct split
7 Correct 144 ms 24912 KB ok, correct split
8 Correct 177 ms 23032 KB ok, correct split
9 Correct 141 ms 20856 KB ok, correct split
10 Correct 85 ms 18672 KB ok, correct split
11 Correct 85 ms 18672 KB ok, correct split
12 Correct 89 ms 19056 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 124 ms 19448 KB invalid split: #1=6, #2=40000, #3=59994
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7544 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 Incorrect 153 ms 26744 KB invalid split: #1=62088, #2=4579, #3=33333
8 Halted 0 ms 0 KB -