Submission #293780

#	Time	Username	Problem	Language	Result	Execution time	Memory
293780		egekabas	Split the Attractions (IOI19_split)	C++14	22 / 100	631 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
using namespace std;
vector<pii> col;
vector<int> ans;
int sz[100009];
vector<int> g[100009];
void calcsz(int v, int prt){
	sz[v] = 1;
	for(auto u : g[v])
		if(u != prt){
			calcsz(u, v);
			sz[v] += sz[u];
		}
}
int lft, use;
void paint(int v, int prt){
	if(lft <= 0) return;
	ans[v] = use;
	--lft;
	for(auto u : g[v])
		if(u != prt){
			paint(u, v);
		}
}
int ok = 0;
int N;
void dfs(int v, int prt){
	if(ok) return;
	for(auto u : g[v]){
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
		swap(col[0], col[1]);
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
	}
	for(auto u : g[v]){
		if(u == prt) continue;
		int vbef = sz[v];
		int ubef = sz[u];
		sz[v] -= sz[u];
		sz[u] += sz[v];
		dfs(u, v);
		sz[v] = vbef;
		sz[u] = ubef;
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	ans.resize(n);
	col = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(col));
	for(int i = 0; i < p.size(); ++i){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	calcsz(0, -1);
	dfs(0, -1);
	if(ok == 0) return ans;
	for(auto &u : ans)
		if(u == 0)
			u = col[2].ss;
	return ans;
}

Compilation message (stderr)

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

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