oj.uz

Submission #156546

# Submission time Handle Problem Language Result Execution time Memory
156546 2019-10-06T12:18:12 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
22 / 100
 893 ms 1048580 KB 
#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector< vector< int > > Graph;
vector< pair<int, int> > v(3);

vector< int > subGraph;

vector< int > ans;

void coloring(int node, int parent, int color, int index){
	if(v[index].first){
		v[index].first--;
		ans[node] = color;
	}else{
		ans[node] = v[2].second;
	}
	
	for(int a : Graph[node]){
		if(a == parent) continue;
		coloring(a, node, color, index);
	}
}

bool dfs(int node, int last){
	int N = Graph.size();
	subGraph[node] = 1;
	
	//cout << "VISITING " << node << endl;
	
	for(int a : Graph[node]){
		if(a == last) continue;
		
		if(dfs(a, node)){
			return true;
		}
		
		subGraph[node] += subGraph[a];
	}
	
	//cout << "NODE " << node << ' ' << "LAST " << last << " SUBGRAPH " << subGraph[node] << endl;
	
	if(subGraph[node] >= v[0].first && N-subGraph[node] >= v[1].first){
		coloring(node, last, v[0].second, 0);
		coloring(last, node, v[1].second, 1);
		return true;
	}else if(subGraph[node] >= v[1].first && N-subGraph[node] >= v[0].first){
		coloring(node, last, v[1].second, 1);
		coloring(last, node, v[0].second, 0);
		return true;
	}
	return false;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	
	Graph.resize(N);
	ans.resize(N);
	subGraph.resize(N);
	
	for(int i = 0; i < (int) p.size(); i++){
		Graph[p[i]].push_back(q[i]);
		Graph[q[i]].push_back(p[i]);
	}
	
	v[0] = {a, 1};
	v[1] = {b, 2};
	v[2] = {c, 3};
	
	sort(v.begin(), v.end());
	
	dfs(0,-1);
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Runtime error 891 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Runtime error 881 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB ok, correct split
2 Correct 82 ms 8668 KB ok, correct split
3 Correct 30 ms 4216 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 86 ms 12792 KB ok, correct split
6 Correct 83 ms 12536 KB ok, correct split
7 Correct 85 ms 12584 KB ok, correct split
8 Correct 85 ms 13944 KB ok, correct split
9 Correct 86 ms 12364 KB ok, correct split
10 Correct 25 ms 3452 KB ok, no valid answer
11 Correct 36 ms 4984 KB ok, no valid answer
12 Correct 67 ms 9976 KB ok, no valid answer
13 Correct 75 ms 9848 KB ok, no valid answer
14 Correct 60 ms 10096 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Runtime error 891 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -