oj.uz

Submission #296145

# Submission time Handle Problem Language Result Execution time Memory
296145 2020-09-10T10:23:40 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
53 / 100
 248 ms 31096 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

vector< int > U;
vector< int > unionSize;

int getParents(int a){
	if(U[a] == a) return a;
	else return U[a] = getParents(U[a]);
}

void Union(int a, int b){
	if(getParents(a) == getParents(b)) return;
	unionSize[getParents(b)] += unionSize[getParents(a)];
	U[getParents(a)] = getParents(b);
}

void compute_tree(int root, int last, vector< bool > &visited, vector< vector< int > > &Graph, vector< vector< int > > &Tree, vector< pair<int, int> > &back_edges){
		visited[root] = true;
		for(int a : Graph[root]){
			if(visited[a] && a != last){
				back_edges.push_back({root, a});
				continue;
			}else if(visited[a]) continue;
			Tree[root].push_back(a);
			Tree[a].push_back(root);
			compute_tree(a,root, visited, Graph, Tree, back_edges);
		}
		
}

void compute_subtrees(int root, int last, vector< vector< int > > &Tree, vector< int > &dp){
	//cout << "ROOT " << root << ' ' << last << endl;
	for(int a : Tree[root]){
		if(a == last){
			continue;
		}
		else{
			compute_subtrees(a, root, Tree, dp);
			dp[root] += dp[a];
		}
	}
}

int find_centroid(int root, int last, vector< vector< int > > &Tree, vector< int > &dp, int &n){
	
	for(int a : Tree[root]){
		if(a == last) continue;
		if(dp[a] > n/2){
			return find_centroid(a, root, Tree,dp,n);
		}
	}
	return root;
}

void compute_centroid_graph(int root, vector< vector< int > > &Tree, vector< vector< int > > &centroidGraph,vector< bool > &visitedCentroid, const int &centroid, vector< pair<int, int> > &centroidEdges){
	visitedCentroid[root] = true;
	for(int a : Tree[root]){
		if(visitedCentroid[a]) continue;
		if(a == centroid){
			centroidEdges.push_back({a,root});
			continue;
		}
		//cout << "ROOT " << root << " " << a << endl;
		centroidGraph[a].push_back(root);
		centroidGraph[root].push_back(a);
		compute_centroid_graph(a, Tree, centroidGraph, visitedCentroid, centroid, centroidEdges);
	}
}

int computeSizeSubtree(int root, vector< vector< int > > &centroidGraph, vector< bool > &visitedSubset, const int bigRoot){
	int tot = 1;
	visitedSubset[root] = true;
	Union(root, bigRoot);
	//cout << "SUBTREE " << root << endl;
	//cout << centroidGraph[root].size() << endl;
	for(int a : centroidGraph[root]){
		if(visitedSubset[a]) continue;
		//cout << root << ' ' << a << endl;
		tot += computeSizeSubtree(a, centroidGraph, visitedSubset, bigRoot);
	}
	return tot;
}

void colourGraph(int root, vector< vector< int > > &centroidGraph, vector< bool > &visitedColouring, vector< int > &ans, const int colour, int &total){
	if(total == 0) return;
	visitedColouring[root] = true;
	ans[root] = colour;
	total--;
	//cout << "COLOURING " << root << " in " << colour << endl;
	if(total == 0) return;
	for(int a : centroidGraph[root]){
		if(visitedColouring[a]) continue;
		colourGraph(a, centroidGraph, visitedColouring, ans, colour, total);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	
	vector< pair<int, int> > sorting = {{a,1},{b,2},{c,3}};
	sort(sorting.begin(), sorting.end());
	a = sorting[0].first;
	b = sorting[1].first;
	c = sorting[2].first;
	
	vector< vector< int > > Graph(n);
	vector< bool > visited(n,false);
	
	for(int i = 0; i < (int)p.size(); i++){
		Graph[p[i]].push_back(q[i]);
		Graph[q[i]].push_back(p[i]);
	}
	
	//TRANSFORM THE GRAPH TO A TREE
	
	vector< vector< int > > Tree(n);
	vector< pair<int, int> > back_edges;
	//cout << "OK" << endl;
	compute_tree(0,-1, visited, Graph, Tree, back_edges);
	//cout << "OK" << endl;
	//for(auto e: back_edges) cout << e.first << ' ' << e.second << endl;
	
	//COMPUTE SIZE OF SUBTREES
	
	vector< int > dp(n, 1);
	compute_subtrees(0,-1,Tree,dp);
	
	//FIND THE CENTROID
	int centroid = find_centroid(0,-1, Tree, dp,n);
	//cout << "CENTROID " << centroid << endl;
	//COMPUTE CENTROID GRAPH
	vector< vector< int > > centroidGraph(n);
	vector< bool > visitedCentroid(n,false);
	
	vector< pair<int, int> > centroidEdges;
	
	for(int i = 0; i < n; i++){
		if(!visitedCentroid[i] && i != centroid){
			compute_centroid_graph(i,Tree, centroidGraph,visitedCentroid, centroid, centroidEdges);
		}
	}
	//COMPUTE SIZE AND ROOT OF EACH SUBSET
	
	U.resize(n);
	unionSize.resize(n,1);
	for(int i = 0; i < n; i++) U[i] = i;
	
	vector< pair<int, int> > sizeAndRootOfSubset;
	vector< bool > visitedSubset(n, false);
	
	for(int i = 0; i < n; i++){
		if(!visitedSubset[i]){
			int size = computeSizeSubtree(i, centroidGraph, visitedSubset, i);
			sizeAndRootOfSubset.push_back({size,i});
			//cout << "SIZE " << size << ' ' << "ROOT " << i << endl;
		}
	}
	//cout << "OK" << endl;
	//CHECK IF ONE OF THEM IS SMALLER THAN A
	sort(sizeAndRootOfSubset.begin(), sizeAndRootOfSubset.end());
	if(sizeAndRootOfSubset.back().first >= a){
		vector< int > ans(n,-1);
		vector< bool > visitedColouring(n,false);
		colourGraph(sizeAndRootOfSubset.back().second,  centroidGraph, visitedColouring, ans, sorting[0].second, a);
		assert(a == 0);
		//ADD EDGES TO CENTROID
		for(auto e : centroidEdges){
			centroidGraph[e.first].push_back(e.second);
			centroidGraph[e.second].push_back(e.first);
		}
		int left = b;
		//cout << left << endl;
		colourGraph(centroid, centroidGraph, visitedColouring, ans, sorting[1].second, left);
		assert(left == 0);
		//REPLACE ALL -1 by 3
		for(int &A : ans){
			if(A == -1) A=sorting[2].second;
		}
		return ans;
	}
	for(auto e : back_edges){
		if(e.first == centroid || e.second == centroid) continue;
		centroidGraph[e.first].push_back(e.second);
		centroidGraph[e.second].push_back(e.first);
		if(getParents(e.first) == getParents(e.second)){
			continue;
		}
		else{
			Union(e.first, e.second);
			if(unionSize[getParents(e.first)] >= a){
				vector< int > ans(n,-1);
				vector< bool > visitedColouring(n,false);
				colourGraph(getParents(e.first),  centroidGraph, visitedColouring, ans, sorting[0].second, a);
				
				for(auto E : centroidEdges){
					centroidGraph[E.first].push_back(E.second);
					centroidGraph[E.second].push_back(E.first);
				}
				int left = b;
				colourGraph(centroid, centroidGraph, visitedColouring, ans, sorting[1].second, left);
				assert(left == 0);
				//REPLACE ALL -1 by 3
				for(int &A : ans){
					if(A == -1) A=sorting[2].second;
				}
				return ans;
			}
		}
	}
	vector< int > ans(n);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 207 ms 30584 KB ok, correct split
8 Correct 207 ms 27512 KB ok, correct split
9 Correct 194 ms 26428 KB ok, correct split
10 Correct 207 ms 31096 KB ok, correct split
11 Correct 248 ms 31096 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 227 ms 27264 KB ok, correct split
5 Correct 175 ms 20472 KB ok, correct split
6 Correct 214 ms 31096 KB ok, correct split
7 Correct 214 ms 27128 KB ok, correct split
8 Correct 238 ms 23788 KB ok, correct split
9 Correct 178 ms 20472 KB ok, correct split
10 Correct 115 ms 22892 KB ok, correct split
11 Correct 109 ms 22892 KB ok, correct split
12 Incorrect 107 ms 23020 KB invalid split: #1=0, #2=50001, #3=49999

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 177 ms 20592 KB ok, correct split
3 Correct 51 ms 8568 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 192 ms 23928 KB ok, correct split
6 Correct 184 ms 23672 KB ok, correct split
7 Correct 184 ms 23288 KB ok, correct split
8 Correct 195 ms 25084 KB ok, correct split
9 Correct 189 ms 23032 KB ok, correct split
10 Correct 42 ms 7168 KB ok, no valid answer
11 Correct 67 ms 10616 KB ok, no valid answer
12 Correct 129 ms 19960 KB ok, no valid answer
13 Correct 154 ms 20600 KB ok, no valid answer
14 Correct 109 ms 19820 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, no valid answer
3 Correct 1 ms 256 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 1 ms 256 KB ok, correct split
8 Correct 0 ms 256 KB ok, correct split
9 Correct 4 ms 1024 KB ok, correct split
10 Correct 4 ms 896 KB ok, correct split
11 Correct 1 ms 384 KB ok, correct split
12 Correct 4 ms 896 KB ok, correct split
13 Correct 0 ms 256 KB ok, correct split
14 Correct 0 ms 256 KB ok, correct split
15 Correct 1 ms 384 KB ok, correct split
16 Correct 1 ms 384 KB ok, correct split
17 Correct 0 ms 256 KB ok, correct split
18 Correct 1 ms 384 KB ok, correct split
19 Correct 1 ms 384 KB ok, correct split
20 Correct 2 ms 512 KB ok, correct split
21 Correct 3 ms 896 KB ok, correct split
22 Correct 3 ms 896 KB ok, correct split
23 Correct 3 ms 896 KB ok, correct split
24 Correct 3 ms 896 KB ok, correct split
25 Correct 3 ms 896 KB ok, correct split
26 Correct 4 ms 1024 KB ok, correct split
27 Correct 3 ms 1024 KB ok, correct split
28 Correct 4 ms 896 KB ok, correct split
29 Correct 1 ms 384 KB ok, correct split
30 Correct 4 ms 1024 KB ok, correct split
31 Correct 2 ms 512 KB ok, correct split
32 Correct 1 ms 384 KB ok, correct split
33 Correct 1 ms 384 KB ok, correct split
34 Correct 3 ms 896 KB ok, correct split
35 Correct 3 ms 896 KB ok, correct split
36 Correct 3 ms 768 KB ok, correct split
37 Correct 4 ms 896 KB ok, correct split
38 Correct 4 ms 1024 KB ok, correct split
39 Correct 5 ms 896 KB ok, correct split
40 Correct 4 ms 896 KB ok, correct split
41 Correct 2 ms 640 KB ok, correct split
42 Correct 2 ms 640 KB ok, correct split
43 Correct 4 ms 896 KB ok, correct split
44 Correct 4 ms 896 KB ok, correct split
45 Correct 4 ms 896 KB ok, correct split
46 Correct 3 ms 896 KB ok, correct split
47 Correct 3 ms 1024 KB ok, no valid answer
48 Correct 4 ms 896 KB ok, correct split
49 Correct 3 ms 1024 KB ok, correct split
50 Correct 1 ms 256 KB ok, no valid answer
51 Correct 1 ms 256 KB ok, no valid answer
52 Correct 3 ms 908 KB ok, no valid answer
53 Correct 5 ms 1024 KB ok, no valid answer
54 Correct 2 ms 896 KB ok, no valid answer
55 Correct 4 ms 896 KB ok, no valid answer
56 Correct 3 ms 896 KB ok, no valid answer

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 207 ms 30584 KB ok, correct split
8 Correct 207 ms 27512 KB ok, correct split
9 Correct 194 ms 26428 KB ok, correct split
10 Correct 207 ms 31096 KB ok, correct split
11 Correct 248 ms 31096 KB ok, correct split
12 Correct 1 ms 256 KB ok, correct split
13 Correct 0 ms 256 KB ok, correct split
14 Correct 1 ms 256 KB ok, correct split
15 Correct 227 ms 27264 KB ok, correct split
16 Correct 175 ms 20472 KB ok, correct split
17 Correct 214 ms 31096 KB ok, correct split
18 Correct 214 ms 27128 KB ok, correct split
19 Correct 238 ms 23788 KB ok, correct split
20 Correct 178 ms 20472 KB ok, correct split
21 Correct 115 ms 22892 KB ok, correct split
22 Correct 109 ms 22892 KB ok, correct split
23 Incorrect 107 ms 23020 KB invalid split: #1=0, #2=50001, #3=49999