oj.uz

Submission #198501

# Submission time Handle Problem Language Result Execution time Memory
198501 2020-01-26T12:16:55 Z Akashi Split the Attractions (IOI19_split) C++14
40 / 100
 226 ms 27764 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int SZ = 2e5 + 5;

vector <int> v[SZ];

int n;
int d[SZ], Max[SZ], TT[SZ];
bool viz[SZ];

void dfs(int nod){
	viz[nod] = 1; d[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		TT[it] = nod;
		dfs(it);
		d[nod] += d[it];
		Max[nod] = max(Max[nod], d[it]);
	}
}

int find_centroid(int nod){
	viz[nod] = 1;
	
	if(max(Max[nod], n - d[nod]) <= n / 2) return nod;
	
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		int x = find_centroid(it);
		if(x) return x;
	}
	
	return 0;
}

vector <int> comp[SZ];
int id[SZ], RG[SZ];

inline int find(int x){
	int R = x;
	while(R != id[R]) R = id[R];
	
	while(id[x] != R){
		int aux = id[x];
		id[x] = R;
		x = aux;
	}
	return R;
}

inline void unite(int x, int y){
	if(x == y) return ;
	if(RG[x] >= RG[y]) id[y] = x, RG[x] += RG[y];
	else id[x] = y, RG[y] += RG[x];
}

void make_comp(int nod, int NR){
	comp[NR].push_back(nod);
	
	viz[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		unite(find(it), find(nod));
		make_comp(it, NR);
	}
}

bool merge_comp(int nod, int &am, int a){
	viz[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		if(find(it) == find(nod)) merge_comp(it, am, a);
		else{
			unite(find(nod), find(it));
			am = RG[find(nod)];
			if(am >= a) return 1;
			merge_comp(it, am, a);
		}
	}
	return 0;
}

int cul[SZ];
void paint_comp(int nod, int &rem, int c){
	if(rem == 0) return ;
	viz[nod] = 1;
	--rem;
	cul[nod] = c;
	
	for(auto it : v[nod]){
		if(viz[it] || cul[it] || find(it) != find(nod)) continue ;
		if(rem) paint_comp(it, rem, c);
	}
}

vector<int> res;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	res.resize(n);
	int m = p.size();
	for(int i = 0; i < m ; ++i){
		v[p[i] + 1].push_back(q[i] + 1);
		v[q[i] + 1].push_back(p[i] + 1);
	}
		
	int ca = 1, cb = 2, cc = 3;
	if(a > b) swap(a, b), swap(ca, cb);
	if(a > c) swap(a, c), swap(ca, cc);
	if(b > c) swap(b, c), swap(cb, cc);
	
	for(int i = 1; i <= n ; ++i) id[i] = i, RG[i] = 1;
	
	dfs(1);
	memset(viz, 0, sizeof(viz));
	int nod = find_centroid(1);
	memset(viz, 0, sizeof(viz));
	dfs(nod);
	
	memset(viz, 0, sizeof(viz));
	int NR = 0;
	viz[nod] = 1;
	for(auto it : v[nod]){
		make_comp(it, NR);
		NR++;
	}
	
	bool found = false;
	int wh = 0;
	for(int i = 0; i < NR ; ++i){
		if(comp[i].size() >= a){
			found = true;
			wh = comp[i][0];
			break ;
		}
	}
	
	////cerr << found << endl;
	if(!found){
		memset(viz, 0, sizeof(viz));
		viz[nod] = 1;
		for(int i = 0; i < NR ; ++i){
			int x = comp[i].size();
			bool ok = merge_comp(comp[i][0], x, a);
			if(ok){
				wh = comp[i][0];
				break ;
			}
		}
	}
	
	if(wh == 0) return res;
	
	memset(viz, 0, sizeof(viz));
	viz[nod] = 1;
	paint_comp(wh, a, ca);
	for(int i = 1; i <= n ; ++i) unite(find(i), find(wh));
	memset(viz, 0, sizeof(viz));
	paint_comp(nod, b, cb);
	
	for(int i = 0; i < n ; ++i){
		if(cul[i + 1] == 0) cul[i + 1] = cc; 
		res[i] = cul[i + 1];
	}
	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:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(comp[i].size() >= a){
      ~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB ok, correct split
2 Correct 11 ms 9976 KB ok, correct split
3 Correct 11 ms 9976 KB ok, correct split
4 Correct 11 ms 9976 KB ok, correct split
5 Correct 12 ms 9976 KB ok, correct split
6 Correct 11 ms 9976 KB ok, correct split
7 Correct 164 ms 23028 KB ok, correct split
8 Correct 159 ms 23000 KB ok, correct split
9 Correct 174 ms 23028 KB ok, correct split
10 Correct 178 ms 27640 KB ok, correct split
11 Correct 208 ms 27636 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9980 KB ok, correct split
2 Correct 10 ms 9976 KB ok, correct split
3 Correct 11 ms 9976 KB ok, correct split
4 Correct 187 ms 23908 KB ok, correct split
5 Correct 136 ms 18424 KB ok, correct split
6 Correct 185 ms 27764 KB ok, correct split
7 Correct 194 ms 23028 KB ok, correct split
8 Correct 226 ms 20724 KB ok, correct split
9 Correct 174 ms 18312 KB ok, correct split
10 Correct 87 ms 20848 KB ok, correct split
11 Correct 86 ms 20976 KB ok, correct split
12 Correct 88 ms 20848 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9976 KB ok, correct split
2 Correct 126 ms 18380 KB ok, correct split
3 Correct 44 ms 13308 KB ok, correct split
4 Correct 11 ms 9976 KB ok, correct split
5 Correct 176 ms 21112 KB ok, correct split
6 Correct 173 ms 21112 KB ok, correct split
7 Correct 181 ms 21204 KB ok, correct split
8 Correct 179 ms 21112 KB ok, correct split
9 Correct 177 ms 21240 KB ok, correct split
10 Correct 40 ms 12664 KB ok, no valid answer
11 Correct 55 ms 14584 KB ok, no valid answer
12 Correct 112 ms 20852 KB ok, no valid answer
13 Correct 132 ms 19528 KB ok, no valid answer
14 Correct 84 ms 21744 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9976 KB ok, correct split
2 Correct 11 ms 9976 KB ok, no valid answer
3 Correct 11 ms 9976 KB ok, correct split
4 Correct 12 ms 9980 KB ok, correct split
5 Correct 12 ms 9976 KB ok, correct split
6 Correct 12 ms 9976 KB ok, correct split
7 Correct 12 ms 9976 KB ok, correct split
8 Correct 12 ms 9976 KB ok, correct split
9 Correct 15 ms 10232 KB ok, correct split
10 Correct 15 ms 10232 KB ok, correct split
11 Correct 13 ms 9976 KB ok, correct split
12 Incorrect 14 ms 10236 KB invalid split: #1=800, #2=1596, #3=5
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB ok, correct split
2 Correct 11 ms 9976 KB ok, correct split
3 Correct 11 ms 9976 KB ok, correct split
4 Correct 11 ms 9976 KB ok, correct split
5 Correct 12 ms 9976 KB ok, correct split
6 Correct 11 ms 9976 KB ok, correct split
7 Correct 164 ms 23028 KB ok, correct split
8 Correct 159 ms 23000 KB ok, correct split
9 Correct 174 ms 23028 KB ok, correct split
10 Correct 178 ms 27640 KB ok, correct split
11 Correct 208 ms 27636 KB ok, correct split
12 Correct 12 ms 9980 KB ok, correct split
13 Correct 10 ms 9976 KB ok, correct split
14 Correct 11 ms 9976 KB ok, correct split
15 Correct 187 ms 23908 KB ok, correct split
16 Correct 136 ms 18424 KB ok, correct split
17 Correct 185 ms 27764 KB ok, correct split
18 Correct 194 ms 23028 KB ok, correct split
19 Correct 226 ms 20724 KB ok, correct split
20 Correct 174 ms 18312 KB ok, correct split
21 Correct 87 ms 20848 KB ok, correct split
22 Correct 86 ms 20976 KB ok, correct split
23 Correct 88 ms 20848 KB ok, correct split
24 Correct 11 ms 9976 KB ok, correct split
25 Correct 126 ms 18380 KB ok, correct split
26 Correct 44 ms 13308 KB ok, correct split
27 Correct 11 ms 9976 KB ok, correct split
28 Correct 176 ms 21112 KB ok, correct split
29 Correct 173 ms 21112 KB ok, correct split
30 Correct 181 ms 21204 KB ok, correct split
31 Correct 179 ms 21112 KB ok, correct split
32 Correct 177 ms 21240 KB ok, correct split
33 Correct 40 ms 12664 KB ok, no valid answer
34 Correct 55 ms 14584 KB ok, no valid answer
35 Correct 112 ms 20852 KB ok, no valid answer
36 Correct 132 ms 19528 KB ok, no valid answer
37 Correct 84 ms 21744 KB ok, no valid answer
38 Correct 11 ms 9976 KB ok, correct split
39 Correct 11 ms 9976 KB ok, no valid answer
40 Correct 11 ms 9976 KB ok, correct split
41 Correct 12 ms 9980 KB ok, correct split
42 Correct 12 ms 9976 KB ok, correct split
43 Correct 12 ms 9976 KB ok, correct split
44 Correct 12 ms 9976 KB ok, correct split
45 Correct 12 ms 9976 KB ok, correct split
46 Correct 15 ms 10232 KB ok, correct split
47 Correct 15 ms 10232 KB ok, correct split
48 Correct 13 ms 9976 KB ok, correct split
49 Incorrect 14 ms 10236 KB invalid split: #1=800, #2=1596, #3=5
50 Halted 0 ms 0 KB -