Submission #143708

#	Time	Username	Problem	Language	Result	Execution time	Memory
143708		qkxwsm	Split the Attractions (IOI19_split)	C++14	40 / 100	113 ms	14940 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 100013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, A, B, C, M, R;
int Z[3];
vi edge[MAXN];
vi ans;
int subtree[MAXN], parent[MAXN];
array<int, 3> ord;

void dfs(int u, int p)
{
	subtree[u] = 1;
	for (int v : edge[u])
	{
		if (v == p) continue;
		parent[v] = u; dfs(v, u);
		subtree[u] += subtree[v];
	}
}

vi find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	N = n; A = a; B = b; C = c; ans.resize(N); M = SZ(p); Z[0] = A; Z[1] = B; Z[2] = C;
	if (A <= B && B <= C) ord = {1, 2, 3};
	if (A <= C && C <= B) ord = {1, 3, 2};
	if (B <= A && A <= C) ord = {2, 1, 3};
	if (B <= C && C <= A) ord = {2, 3, 1};
	if (C <= B && B <= A) ord = {3, 1, 2};
	if (C <= A && A <= B) ord = {3, 2, 1};
	FOR(i, 0, SZ(p))
	{
		int u = p[i], v = q[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	FOR(i, 0, N) ans[i] = 0;
	if (a == 1)
	{
		q.clear(); q.PB(0); b = 0;
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = 2; b++;
			// cerr << "MARK " << u << endl;
			if (b == B) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					// cerr << u << " -> " << v << endl;
					ans[v] = -2;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] != 2) ans[i] = 3;
		}
		FOR(i, 0, N)
		{
			if (ans[i] == 3)
			{
				ans[i] = 1;
				break;
			}
		}
	}
	else if (M == N - 1)
	{
		parent[0] = N;
		dfs(0, N);
		R = -1;
		FOR(i, 0, N)
		{
			int sum = N - 1, mx = 0;
			for (int v : edge[i])
			{
				if (v == parent[i]) continue;
				sum -= subtree[v];
				ckmax(mx, subtree[v]);
			}
			ckmax(mx, sum);
			if (mx <= N / 2) R = i;
		}
		parent[R] = N;
		dfs(R, N);
		//there has to be a connected block that doesn't contain the centroid.
		int mx = 0, ch = -1;
		for (int v : edge[R])
		{
			if (subtree[v] > mx)
			{
				mx = subtree[v];
				ch = v;
			}
		}
		int sz = Z[ord[0] - 1];
		if (mx < sz) return ans;
		//generate any set lol
		ans[R] = -1;
		q.clear(); q.PB(ch);
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = -2; sz--; if (sz == 0) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ans[v] = -1;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] == -2) ans[i] = ord[0];
			else ans[i] = 0;
		}
		q.clear(); q.PB(R);
		sz = Z[ord[1] - 1];
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = -2; sz--; if (sz == 0) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ans[v] = -1;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] == -2) ans[i] = ord[1];
		}
		FOR(i, 0, N)
		{
			if (ans[i] != ord[0] && ans[i] != ord[1]) ans[i] = ord[2];
		}
		//do the exact smae thing except for ord1
	}
	else
	{
		vi ord; ord.PB(0);
		FOR(i, 0, N)
		{
			int u = ord.back(); ans[u] = -1;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ord.PB(v);
					break;
				}
			}
		}
		FOR(i, 0, A) ans[ord[i]] = 1;
		FOR(i, A, A + B) ans[ord[i]] = 2;
		FOR(i, A + B, A + B + C) ans[ord[i]] = 3;
	}
	// cerr << "HUH\n"
	return ans;
}

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