Submission #240878

#	Time	Username	Problem	Language	Result	Execution time	Memory
240878		zoomswk	Split the Attractions (IOI19_split)	C++17	40 / 100	137 ms	15476 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();
	for(int i=0; i<m; i++){
		way[p[i]].push_back(q[i]);
		way[q[i]].push_back(p[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;
		}
	}
	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:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in2.size(); j++){
                 ~^~~~~~~~~~~~~~~~~
split.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<whats_in.size(); j++){
                 ~^~~~~~~~~~~~~~~~
split.cpp:66:18: 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