oj.uz

Submission #296142

# Submission time Handle Problem Language Result Execution time Memory
296142 2020-09-10T10:22:23 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
53 / 100
 223 ms 31352 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);
		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);
				
				//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 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 218 ms 30728 KB ok, correct split
8 Correct 194 ms 27512 KB ok, correct split
9 Correct 209 ms 26636 KB ok, correct split
10 Correct 196 ms 31224 KB ok, correct split
11 Correct 206 ms 31224 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 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 218 ms 27260 KB ok, correct split
5 Correct 168 ms 20856 KB ok, correct split
6 Correct 201 ms 31352 KB ok, correct split
7 Correct 207 ms 27384 KB ok, correct split
8 Correct 223 ms 23788 KB ok, correct split
9 Correct 173 ms 20600 KB ok, correct split
10 Correct 117 ms 22892 KB ok, correct split
11 Correct 114 ms 22892 KB ok, correct split
12 Incorrect 111 ms 23148 KB invalid split: #1=0, #2=50001, #3=49999

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 162 ms 20728 KB ok, correct split
3 Correct 50 ms 8568 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 190 ms 23988 KB ok, correct split
6 Correct 188 ms 23672 KB ok, correct split
7 Correct 210 ms 23416 KB ok, correct split
8 Correct 190 ms 25208 KB ok, correct split
9 Correct 191 ms 23288 KB ok, correct split
10 Correct 40 ms 7160 KB ok, no valid answer
11 Correct 68 ms 10488 KB ok, no valid answer
12 Correct 135 ms 20088 KB ok, no valid answer
13 Correct 159 ms 20856 KB ok, no valid answer
14 Correct 127 ms 19948 KB ok, no valid answer

Subtask #4
24.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 1 ms 256 KB ok, correct split
4 Correct 1 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 1 ms 256 KB ok, correct split
9 Correct 5 ms 1024 KB ok, correct split
10 Correct 5 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 256 KB ok, correct split
17 Correct 0 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 512 KB ok, correct split
21 Correct 4 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 4 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 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 5 ms 1024 KB ok, correct split
39 Correct 4 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 5 ms 896 KB ok, correct split
46 Correct 3 ms 896 KB ok, correct split
47 Correct 4 ms 896 KB ok, no valid answer
48 Correct 3 ms 896 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 0 ms 256 KB ok, no valid answer
52 Correct 3 ms 896 KB ok, no valid answer
53 Correct 5 ms 1024 KB ok, no valid answer
54 Correct 2 ms 892 KB ok, no valid answer
55 Correct 3 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 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 218 ms 30728 KB ok, correct split
8 Correct 194 ms 27512 KB ok, correct split
9 Correct 209 ms 26636 KB ok, correct split
10 Correct 196 ms 31224 KB ok, correct split
11 Correct 206 ms 31224 KB ok, correct split
12 Correct 1 ms 256 KB ok, correct split
13 Correct 1 ms 256 KB ok, correct split
14 Correct 1 ms 256 KB ok, correct split
15 Correct 218 ms 27260 KB ok, correct split
16 Correct 168 ms 20856 KB ok, correct split
17 Correct 201 ms 31352 KB ok, correct split
18 Correct 207 ms 27384 KB ok, correct split
19 Correct 223 ms 23788 KB ok, correct split
20 Correct 173 ms 20600 KB ok, correct split
21 Correct 117 ms 22892 KB ok, correct split
22 Correct 114 ms 22892 KB ok, correct split
23 Incorrect 111 ms 23148 KB invalid split: #1=0, #2=50001, #3=49999