Submission #1146909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146909		monkey133	Split the Attractions (IOI19_split)	C++20	100 / 100	91 ms	17732 KiB

split

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<ll> adj[100005];
ll siz[5],  lab[5];
ll sub[100005], status[100005];

ll find_centroid(ll x = 0)
{
	//show(x);
	sub[x] = 1;
	status[x] = 0;
	for (ll u: adj[x]) if (status[u]==-1)
	{
		ll res = find_centroid(u);
		sub[x] += sub[u];
		if (sub[u] >= siz[0]) return res;
	}
	status[x] = 1;
	//show(sub[x]);
	return x;
}

void paint(ll x,  ll prevv, ll neww)
{
	if (siz[neww]==0) return;
	//show3(x, prevv, neww);
	//show(siz[neww]);
	siz[neww]--;
	status[x] = lab[neww];
	for (ll u: adj[x]) if (status[u]==prevv) paint(u, prevv, neww);
}

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q)
{
	for (ll i=0; i<n; ++i) adj[i].clear();
	vector<int> ans(n, 0);
	siz[0] = a, siz[1] = b, siz[2] = c, siz[3] = n;
	lab[0] = 1, lab[1] = 2, lab[2] = 3, lab[3] = 4;
	for (ll i=0; i<2; ++i) {if (siz[i] > siz[i + 1]) {swap(siz[i], siz[i + 1]); swap(lab[i], lab[i + 1]);}}
	for (ll i=1; i>=0; --i) {if (siz[i] > siz[i + 1]) {swap(siz[i], siz[i + 1]); swap(lab[i], lab[i + 1]);}}
	for (ll i=0; i<p.size(); ++i)
	{
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	//show(1);
	fill(status, status+ n, -1);
	ll root = find_centroid();
	//show(root);
	if (root!=0)
	{
		// paint subtree >= a
		paint(root, 1, 3);
		if (sub[root] >= siz[1]) {swap(siz[0], siz[1]); swap(lab[0], lab[1]);}
		// subtree of root -> 4, otheriwse 5
		for (ll i=0; i<n; ++i) status[i] = ((status[i]==4)?4: 5);
		//for (ll i=0; i<n; ++i) show2(i, status[i]);
		// paint subtree outside as 1
		paint(0, 5, 1);
		// add more edges to 1 (if needed) through any backedge
		status[root] = 69;
		for (ll i=0; i<n; ++i) if (status[i]==lab[1]) for (ll u: adj[i]) if (status[u]==4) paint(u, 4, 1);
		// confirm leftover for subtree 0
		status[root] = 4;
		paint(root, 4, 0);
		//for (ll i=0; i<n; ++i) show(status[i]);
	}
	//show2(lab[0], lab[1]);
	//show2(siz[0], siz[1]);
	if (siz[0] != 0 || siz[1]!= 0) return ans;
	for (ll i=0; i<n; ++i) ans[i] = ((status[i]<=3)?status[i]:lab[2]);
	return ans;
}

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