Submission #1064416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064416		Arapak	Split the Attractions (IOI19_split)	C++17	40 / 100	88 ms	15312 KiB

split

// Author: Kajetan Ramsza
#include "split.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, const pair<auto, auto> &p);
auto& operator<<(auto &os, const auto &v) 
	{ os<<"{"; for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) { os<<", "; } os<<(*it);
	} return os<<"}"; }
auto& operator<<(auto &os, const pair<auto, auto> &p) 
	{ return os<<"("<<p.first<<", "<<p.second<<")"; }

void dbg_out(auto... x) { ((cerr<<' '<<x), ...) << endl; }
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif

int n;
vector<vi> g;
vector<bool> visited;
vi siz, parent;

void dfs(int v) {
	visited[v] = true;
	siz[v] = 1;
	for(auto e : g[v]) {
		if(visited[e]) continue;
		dfs(e);
		parent[e] = v;
		siz[v] += siz[e];
	}
}

void shuffle_all() {
	rep(i,0,n) random_shuffle(all(g[i]));
}

void init(int root) {
	shuffle_all();
	parent.assign(n, -1);
	visited.assign(n, 0);
	siz.assign(n, 0);
	dfs(root);
	fill(all(visited), false);
	dbg(parent);
	dbg(siz);
}

int select_k(int v, int k, vi &sel, bool par, int num) {
	dbg(v, k, sel, par, num);
	visited[v] = true;
	k--;
	sel[v] = num;
	for(auto e : g[v]) {
		if(k == 0) break;
		if(visited[e]) continue;
		if(par && parent[e] != v) continue;
		k = select_k(e, k, sel, par, num);
	}
	return k;
}


pair<bool, vi> solve(vi vals, vi order) {
	dbg(vals);
	dbg(order);
	rep(v,0,n) {
		if(parent[v] == -1) continue;
		dbg(v, siz[v], n-siz[v]);

		if(siz[v] >= vals[order[0]] && n-siz[v] >= vals[order[1]]) {
			vi sel(n, order[2]+1);
			select_k(v, vals[order[0]], sel, true, order[0]+1);
			select_k(parent[v], vals[order[1]], sel, false, order[1]+1);
			return {true, sel};
		}

		if(siz[v] >= vals[order[1]] && n-siz[v] >= vals[order[0]]) {
			vi sel(n, order[2]+1);
			select_k(v, vals[order[1]], sel, true, order[1]+1);
			select_k(parent[v], vals[order[0]], sel, false, order[0]+1);
			return {true, sel};
		}
	}
	return {false, {}};
}

const int tries = 10;

vi find_split(int N, int a, int b, int c, vi p, vi q) {
	n = N;
	g.resize(n);
	rep(i,0,sz(p)) {
		g[p[i]].emplace_back(q[i]);
		g[q[i]].emplace_back(p[i]);
	}
	
	vi vals = {a, b, c};
	vi order = {0, 1, 2};
	sort(all(order), [&](int x, int y) {
		return vals[x] < vals[y];
	});

	srand(2137);
	rep(i,0,tries) {
		init(rand() % n);
		auto [poss, vec] = solve(vals, order);
		if(poss) return vec;
	}
	
	return vi(n, 0);
}

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