Submission #240880

#	Time	Username	Problem	Language	Result	Execution time	Memory
240880		zoomswk	Split the Attractions (IOI19_split)	C++17	40 / 100	432 ms	14712 KiB

split

#include "split.h"
#include <vector>
#include <algorithm>
using namespace std;

vector<int> way[100005];
int par[100005];
int sz[100005];

int dfs(int node, int p=-1){
	if(sz[node] > 0) return 0;
	par[node] = p;
	sz[node] = 1;
	for(int x : way[node]) sz[node] += dfs(x, node);
	return sz[node];
}

int is_in[100005];
vector<int> whats_in;
vector<int> whats_in2;

void go(int node){
	is_in[node] = 1;
	whats_in.push_back(node);
	for(int x : way[node]) if(par[x] == node) go(x);
	return;
}

void go2(int node){
	if(is_in[node]) return;
	whats_in2.push_back(node);
	for(int x : way[node]) if(par[x] == node) go2(x);
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = (int)p.size();
	int trials = 20;
	vector<int> perm(m);
	for(int i=0; i<m; i++) perm[i] = i;
	while(trials--){
		for(int i=0; i<n; i++){
			way[i].clear();
			par[i] = 0;
			sz[i] = 0;
			is_in[i] = 0;
		}
		whats_in.clear();
		whats_in2.clear();
		random_shuffle(perm.begin(), perm.end());
		for(int i=0; i<m; i++){
			way[p[perm[i]]].push_back(q[perm[i]]);
			way[q[perm[i]]].push_back(p[perm[i]]);
		}
		dfs(0);
		vector<pair<int, int>> vv = {{a, 1}, {b, 2}, {c, 3}};
		sort(vv.begin(), vv.end());
		vector<int> res(n, 0);
		for(int i=0; i<n; i++){
			if(sz[i] >= vv[0].first && n-sz[i] >= vv[1].first){
				go(i);
				go2(0);
				for(int j=0; j<whats_in.size(); j++){
					if(j < vv[0].first) res[whats_in[j]] = vv[0].second;
					else res[whats_in[j]] = vv[2].second;
				}
				for(int j=0; j<whats_in2.size(); j++){
					if(j < vv[1].first) res[whats_in2[j]] = vv[1].second;
					else res[whats_in2[j]] = vv[2].second;
				}
				return res;
			} else if(sz[i] >= vv[1].first && n-sz[i] >= vv[0].first){
				go(i);
				go2(0);
				for(int j=0; j<whats_in.size(); j++){
					if(j < vv[1].first) res[whats_in[j]] = vv[1].second;
					else res[whats_in[j]] = vv[2].second;
				}
				for(int j=0; j<whats_in2.size(); j++){
					if(j < vv[0].first) res[whats_in2[j]] = vv[0].second;
					else res[whats_in2[j]] = vv[2].second;
				}
				return res;
			}
		}
	}
	vector<int> res(n, 0);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<whats_in.size(); j++){
                  ~^~~~~~~~~~~~~~~~
split.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<whats_in2.size(); j++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<whats_in.size(); j++){
                  ~^~~~~~~~~~~~~~~~
split.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<whats_in2.size(); j++){
                  ~^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36