Submission #1047740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047740		vjudge1	Split the Attractions (IOI19_split)	C++17	40 / 100	48 ms	28144 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 200005

vector<int> adj[MAXN];
vector<int> child[MAXN];
int res[MAXN], vis[MAXN], sz[MAXN];

const int modulo = 1e9 + 7;

void dfs(int node){
	sz[node] = 1;
	vis[node] = 1;
	for (auto i : adj[node]){
		if (vis[i] == 0) {
			child[node].pb(i);
			dfs(i);
			sz[node] += sz[i];
		}
	}
}

void color(int node, int &cnt, int c){
	if (cnt == 0) return;
	res[node] = c;
	cnt--;
	for (auto i : child[node])
		if (res[i] == 0) color(i, cnt, c);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i = 0; i < p.size(); i++){
		adj[p[i]].pb(q[i]), adj[q[i]].pb(p[i]);
	}

	vector<pii> v = {{a, 1}, {b, 2}, {c, 3}};
	sort(v.rbegin(), v.rend());

	dfs(0);
	pii mini = {modulo, -1};
	for (int i = 0; i < n; i++){
		if (sz[i] >= v[2].st) mini = min(mini, {sz[i], i});
	}

	vector<int> ans(n, 0);
	if (n - mini.st >= v[1].st){
		color(mini.nd, v[2].st, v[2].nd);
		color(0, v[1].st, v[1].nd);
		for (int i = 0; i < n; i++){
			ans[i] = res[i];
			if (ans[i] == 0) ans[i] = v[0].nd;
		}
		return ans;
	}

	mini = {modulo, -1};
	for (int i = 0; i < n; i++){
		if (sz[i] >= v[1].st) mini = min(mini, {sz[i], i});
	}

	if (n - mini.st >= v[2].st){
		color(mini.nd, v[1].st, v[1].nd);
		color(0, v[2].st, v[2].nd);
		for (int i = 0; i < n; i++){
			ans[i] = res[i];
			if (ans[i] == 0) ans[i] = v[0].nd;
		}
		return ans;
	}
	return ans;
}
/*
int main() {
	fileio();
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}*/

Compilation message (stderr)

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

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