oj.uz

Submission #296120

# Submission time Handle Problem Language Result Execution time Memory
296120 2020-09-10T09:52:16 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
22 / 100
 221 ms 31736 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){
	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(1,-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(1,-1,Tree,dp);
	
	//FIND THE CENTROID
	int centroid = find_centroid(1,-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);
		
		//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);
		
		//REPLACE ALL -1 by 3
		for(int &A : ans){
			if(A == -1) A=sorting[2].second;
		}
		return ans;
	}
	for(auto e : back_edges){
		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);
				}
				colourGraph(centroid, centroidGraph, visitedColouring, ans, sorting[1].second, b);
				
				//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
0 / 7.0

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

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 206 ms 27640 KB ok, correct split
5 Correct 158 ms 21112 KB ok, correct split
6 Correct 198 ms 31736 KB ok, correct split
7 Correct 203 ms 28152 KB ok, correct split
8 Correct 221 ms 24300 KB ok, correct split
9 Correct 169 ms 20984 KB ok, correct split
10 Correct 106 ms 23532 KB ok, correct split
11 Correct 113 ms 23404 KB ok, correct split
12 Incorrect 112 ms 23532 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 161 ms 21112 KB ok, correct split
3 Correct 48 ms 8824 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 183 ms 24312 KB ok, correct split
6 Correct 183 ms 24696 KB ok, correct split
7 Correct 183 ms 24824 KB ok, correct split
8 Correct 196 ms 23948 KB ok, correct split
9 Correct 186 ms 24184 KB ok, correct split
10 Correct 40 ms 7424 KB ok, no valid answer
11 Correct 63 ms 10872 KB ok, no valid answer
12 Correct 131 ms 20600 KB ok, no valid answer
13 Correct 152 ms 21112 KB ok, no valid answer
14 Correct 103 ms 20332 KB ok, no valid answer

Subtask #4
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 1 ms 384 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 1 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 1 ms 256 KB ok, correct split
14 Correct 1 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 1 ms 256 KB ok, correct split
18 Correct 1 ms 256 KB ok, correct split
19 Correct 1 ms 384 KB ok, correct split
20 Correct 2 ms 640 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 4 ms 896 KB ok, correct split
26 Incorrect 3 ms 1024 KB invalid split: #1=401, #2=800, #3=1199
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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