답안 #296128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296128	2020-09-10T10:03:32 Z	MoNsTeR_CuBe	Split the Attractions (IOI19_split)	C++17	29 / 100	232 ms	31864 KB

split

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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