oj.uz

Submission #198500

# Submission time Handle Problem Language Result Execution time Memory
198500 2020-01-26T12:10:06 Z Akashi Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 575864 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(nod, am, a);
		else{
			unite(find(nod), find(it));
			am = RG[find(nod)];
			if(am >= a) break ;
			merge_comp(nod, 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> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	vector<int> res(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 12 ms 9976 KB ok, correct split
3 Correct 13 ms 9976 KB ok, correct split
4 Correct 12 ms 9976 KB ok, correct split
5 Correct 12 ms 9976 KB ok, correct split
6 Correct 12 ms 9976 KB ok, correct split
7 Correct 210 ms 22388 KB ok, correct split
8 Correct 191 ms 20980 KB ok, correct split
9 Correct 196 ms 21108 KB ok, correct split
10 Correct 173 ms 23796 KB ok, correct split
11 Correct 192 ms 23796 KB ok, correct split

Subtask #2
11.0 / 11.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 12 ms 9976 KB ok, correct split
4 Correct 223 ms 21104 KB ok, correct split
5 Correct 126 ms 19064 KB ok, correct split
6 Correct 163 ms 23796 KB ok, correct split
7 Correct 182 ms 22260 KB ok, correct split
8 Correct 225 ms 22616 KB ok, correct split
9 Correct 179 ms 19080 KB ok, correct split
10 Correct 86 ms 21232 KB ok, correct split
11 Correct 90 ms 21232 KB ok, correct split
12 Correct 95 ms 21620 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9976 KB ok, correct split
2 Correct 142 ms 19192 KB ok, correct split
3 Correct 53 ms 13560 KB ok, correct split
4 Correct 11 ms 9976 KB ok, correct split
5 Correct 171 ms 20984 KB ok, correct split
6 Correct 204 ms 21056 KB ok, correct split
7 Correct 210 ms 20988 KB ok, correct split
8 Correct 201 ms 21240 KB ok, correct split
9 Correct 187 ms 20984 KB ok, correct split
10 Execution timed out 2266 ms 575864 KB Time limit exceeded
11 Halted 0 ms 0 KB -

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 12 ms 9976 KB ok, correct split
4 Correct 12 ms 9976 KB ok, correct split
5 Correct 11 ms 9976 KB ok, correct split
6 Correct 12 ms 9976 KB ok, correct split
7 Correct 13 ms 9976 KB ok, correct split
8 Correct 12 ms 9976 KB ok, correct split
9 Correct 14 ms 10232 KB ok, correct split
10 Correct 14 ms 10232 KB ok, correct split
11 Correct 12 ms 9976 KB ok, correct split
12 Incorrect 14 ms 10232 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 12 ms 9976 KB ok, correct split
3 Correct 13 ms 9976 KB ok, correct split
4 Correct 12 ms 9976 KB ok, correct split
5 Correct 12 ms 9976 KB ok, correct split
6 Correct 12 ms 9976 KB ok, correct split
7 Correct 210 ms 22388 KB ok, correct split
8 Correct 191 ms 20980 KB ok, correct split
9 Correct 196 ms 21108 KB ok, correct split
10 Correct 173 ms 23796 KB ok, correct split
11 Correct 192 ms 23796 KB ok, correct split
12 Correct 12 ms 9976 KB ok, correct split
13 Correct 11 ms 9976 KB ok, correct split
14 Correct 12 ms 9976 KB ok, correct split
15 Correct 223 ms 21104 KB ok, correct split
16 Correct 126 ms 19064 KB ok, correct split
17 Correct 163 ms 23796 KB ok, correct split
18 Correct 182 ms 22260 KB ok, correct split
19 Correct 225 ms 22616 KB ok, correct split
20 Correct 179 ms 19080 KB ok, correct split
21 Correct 86 ms 21232 KB ok, correct split
22 Correct 90 ms 21232 KB ok, correct split
23 Correct 95 ms 21620 KB ok, correct split
24 Correct 11 ms 9976 KB ok, correct split
25 Correct 142 ms 19192 KB ok, correct split
26 Correct 53 ms 13560 KB ok, correct split
27 Correct 11 ms 9976 KB ok, correct split
28 Correct 171 ms 20984 KB ok, correct split
29 Correct 204 ms 21056 KB ok, correct split
30 Correct 210 ms 20988 KB ok, correct split
31 Correct 201 ms 21240 KB ok, correct split
32 Correct 187 ms 20984 KB ok, correct split
33 Execution timed out 2266 ms 575864 KB Time limit exceeded
34 Halted 0 ms 0 KB -