oj.uz

Submission #296128

# Submission time Handle Problem Language Result Execution time Memory
296128 2020-09-10T10:03:32 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
29 / 100
 232 ms 31864 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);
		
		//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);
				}
				int left = b;
				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;
			}
		}
	}
	vector< int > ans(n);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 0 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 199 ms 31320 KB ok, correct split
8 Correct 199 ms 28156 KB ok, correct split
9 Correct 200 ms 27128 KB ok, correct split
10 Correct 204 ms 31864 KB ok, correct split
11 Correct 231 ms 31864 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 215 ms 26988 KB ok, correct split
5 Correct 168 ms 20472 KB ok, correct split
6 Correct 199 ms 30968 KB ok, correct split
7 Correct 192 ms 27000 KB ok, correct split
8 Correct 232 ms 23404 KB ok, correct split
9 Correct 164 ms 20088 KB ok, correct split
10 Correct 109 ms 22636 KB ok, correct split
11 Correct 111 ms 22892 KB ok, correct split
12 Incorrect 116 ms 22636 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 163 ms 20216 KB ok, correct split
3 Correct 48 ms 8320 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 185 ms 23616 KB ok, correct split
6 Correct 185 ms 23416 KB ok, correct split
7 Correct 200 ms 23032 KB ok, correct split
8 Correct 189 ms 24824 KB ok, correct split
9 Correct 190 ms 22904 KB ok, correct split
10 Correct 40 ms 7036 KB ok, no valid answer
11 Correct 61 ms 10360 KB ok, no valid answer
12 Correct 127 ms 19704 KB ok, no valid answer
13 Correct 171 ms 20344 KB ok, no valid answer
14 Correct 101 ms 19564 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, no valid answer
3 Correct 0 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 0 ms 256 KB ok, correct split
7 Correct 0 ms 256 KB ok, correct split
8 Correct 0 ms 256 KB ok, correct split
9 Correct 4 ms 896 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 0 ms 384 KB ok, correct split
17 Correct 1 ms 256 KB ok, correct split
18 Correct 0 ms 256 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 3 ms 1024 KB ok, correct split
29 Correct 1 ms 384 KB ok, correct split
30 Correct 3 ms 1024 KB ok, correct split
31 Correct 1 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 4 ms 896 KB ok, correct split
36 Correct 4 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 4 ms 1024 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 896 KB ok, no valid answer
48 Correct 3 ms 900 KB ok, correct split
49 Correct 3 ms 1024 KB ok, correct split
50 Correct 0 ms 256 KB ok, no valid answer
51 Correct 1 ms 256 KB ok, no valid answer
52 Correct 3 ms 896 KB ok, no valid answer
53 Correct 4 ms 1024 KB ok, no valid answer
54 Correct 2 ms 896 KB ok, no valid answer
55 Incorrect 4 ms 896 KB invalid split: #1=832, #2=833, #3=834
56 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 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 0 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 199 ms 31320 KB ok, correct split
8 Correct 199 ms 28156 KB ok, correct split
9 Correct 200 ms 27128 KB ok, correct split
10 Correct 204 ms 31864 KB ok, correct split
11 Correct 231 ms 31864 KB ok, correct split
12 Correct 0 ms 256 KB ok, correct split
13 Correct 0 ms 256 KB ok, correct split
14 Correct 0 ms 256 KB ok, correct split
15 Correct 215 ms 26988 KB ok, correct split
16 Correct 168 ms 20472 KB ok, correct split
17 Correct 199 ms 30968 KB ok, correct split
18 Correct 192 ms 27000 KB ok, correct split
19 Correct 232 ms 23404 KB ok, correct split
20 Correct 164 ms 20088 KB ok, correct split
21 Correct 109 ms 22636 KB ok, correct split
22 Correct 111 ms 22892 KB ok, correct split
23 Incorrect 116 ms 22636 KB invalid split: #1=0, #2=50001, #3=49999