oj.uz

Submission #295009

# Submission time Handle Problem Language Result Execution time Memory
295009 2020-09-09T12:08:07 Z theStaticMind Split the Attractions (IOI19_split) C++14
22 / 100
 683 ms 1048580 KB 
#include<bits/stdc++.h>
#include "split.h"

using namespace std;

vector<int> ans;
vector<int> adj[100000];
vector<int> sub(100000, 1);
vector<int> d(100005, 0);
void dfs(int x, int pre){
	for(auto y : adj[x]){
		if(y == pre) continue;
		d[y] = d[x] + 1;
		dfs(y, x);
		sub[x] += sub[y];
	}
}

void greedy(int x, int& rem, int v){
	if(!rem) return;
	ans[x] = v;
	rem--;
	for(auto y : adj[x]){
		if(ans[y]) continue;
		greedy(y, rem, v);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> u, vector<int> v) {
	ans = vector<int>(n, 0);
	int w[3] = {a, b, c};
	vector<int> q = {0, 1, 2};
	sort(q.begin(), q.end(), [&](int x, int y){return w[x] < w[y];});

	for(int i = 0; i < u.size(); i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, -1);

	vector<int> seq(n);
	for(int i = 0; i < n; i++){
		seq[i] = i;
	}
	sort(seq.begin(), seq.end(), [&](int x, int y){return sub[x] < sub[y];});

	int t1 = 0, t2 = 0;
	for(auto x : seq){
		if(sub[x] >= w[q[0]]){
			t1 = x;
			break;
		}
	}
	for(auto x : seq){
		if(sub[x] >= w[q[1]]){
			t2 = x;
			break;
		}
	}
	if(n - sub[t1] >= w[q[1]]){
		ans[t1] = q[0] + 1;
		greedy(0, w[q[1]], q[1] + 1);
		greedy(t1, w[q[0]], q[0] + 1);
	}
	else if(n - sub[t2] >= w[q[0]]){
		ans[t2] = q[1] + 1;
		greedy(0, w[q[0]], q[0] + 1);
		greedy(t2, w[q[1]], q[1] + 1);
	}
	else{
		return ans;
	}

	for(int i = 0; i < n; i++){
		if(!ans[i]) ans[i] = q[2] + 1;
	}

	return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB ok, correct split
2 Runtime error 683 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB ok, correct split
2 Runtime error 636 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB ok, correct split
2 Correct 94 ms 10616 KB ok, correct split
3 Correct 30 ms 6264 KB ok, correct split
4 Correct 3 ms 3456 KB ok, correct split
5 Correct 122 ms 12596 KB ok, correct split
6 Correct 120 ms 12448 KB ok, correct split
7 Correct 111 ms 12152 KB ok, correct split
8 Correct 114 ms 13304 KB ok, correct split
9 Correct 115 ms 12024 KB ok, correct split
10 Correct 25 ms 5760 KB ok, no valid answer
11 Correct 37 ms 7032 KB ok, no valid answer
12 Correct 76 ms 10740 KB ok, no valid answer
13 Correct 84 ms 10616 KB ok, no valid answer
14 Correct 64 ms 10928 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 638 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB ok, correct split
2 Runtime error 683 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -