Submission #172080

#	Time	Username	Problem	Language	Result	Execution time	Memory
172080		qkxwsm	Split the Attractions (IOI19_split)	C++14	0 / 100	15 ms	14456 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 200013

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, X, Y, T, C;
int siz[3];
pii inds;
vi edge[MAXN], edge1[MAXN];
vi ans;
int st[MAXN], ft[MAXN];
bitset<MAXN> seen;
vi bcc[MAXN];
int parent[MAXN], subtree[MAXN];
vpi edges;
int mnmx, cent;

void dfs(int u, int p)
{
	st[u] = T;
	ft[u] = T;
	T++;
	seen[u] = true;
	for (int v : edge[u])
	{
		if (v == p) continue;
		if (seen[v])
		{
			if (st[v] > st[u]) continue;
			edges.PB({u, v});
			ckmin(ft[u], st[v]);
			continue;
		}
		edges.PB({u, v});
		dfs(v, u);
		ckmin(ft[u], ft[v]);
		if (ft[v] >= st[u])
		{
			while(!edges.empty())
			{
				pii p = edges.back();
				edges.pop_back();
				bcc[p.fi].PB(C);
				bcc[p.se].PB(C);
				if (p == MP(u, v)) break;
			}
			C++;
		}
	}
}
void dfs1(int u, int p, bool flag)
{
	subtree[u] = (u < N);
	for (int v : edge1[u])
	{
		if (v == p) continue;
		parent[v] = u;
		dfs1(v, u, flag);
		subtree[u] += subtree[v];
	}
	if (u < N && flag)
	{
		int sz = N - 1, mx = 0;
		vi szs;
		for (int v : edge1[u])
		{
			ckmax(mx, subtree[v]);
			sz -= subtree[v];
		}
		ckmax(mx, sz);
		if (mx < mnmx)
		{
			mnmx = mx;
			cent = u;
		}
	}
	return;
}

vi find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	N = n;
	ans.resize(N);
	siz[0] = a; siz[1] = b; siz[2] = c;
	if (c >= a && c >= b) inds = {0, 1};
	if (b >= a && b >= c) inds = {0, 2};
	if (a >= b && a >= c) inds = {1, 2};
	X = siz[inds.fi]; Y = siz[inds.se];
	if (X > Y)
	{
		swap(inds.fi, inds.se);
		swap(X, Y);
	}
	FOR(i, 0, SZ(p))
	{
		int u = p[i], v = q[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	dfs(0, N);
	FOR(i, 0, N)
	{
		sort(ALL(bcc[i]));
		bcc[i].erase(unique(ALL(bcc[i])), bcc[i].end());
		for (int x : bcc[i])
		{
			// cerr << "EDGE " << i << " -> " << x + N << endl;
			edge1[i].PB(x + N);
			edge1[x + N].PB(i);
		}
	}
	mnmx = N;
	dfs1(0, N, true);
	if (mnmx < X)
	{
		return ans;
	}
	// cerr << "CENTROID " << cent << endl;
	// cerr << "HELLO\n";
	dfs1(cent, N, false);
	// cerr << "CENT " << cent << endl;
	ans[cent] = 2;
	int source = -1;
	// cerr << "segfault\n";
	for (int v : edge1[cent])
	{
		// cerr << "v = " << v << endl;
		if (subtree[v] < X) continue;
		for (int w : edge1[v])
		{
			if (w != cent) source = w;
		}
	}
	// cerr << "SOURCE " << source << endl;
	q.clear();
	ans[source] = 1;
	q.PB(source);
	X--;
	while(X > 0)
	{
		int u = q.back(); q.pop_back();
		for (int v : edge[u])
		{
			if (ans[v]) continue;
			ans[v] = 1;
			q.PB(v);
			X--;
			if (X == 0) break;
		}
	}
	q.clear();
	ans[cent] = 2;
	q.PB(cent);
	Y--;
	while(Y > 0)
	{
		int u = q.back(); q.pop_back();
		for (int v : edge[u])
		{
			if (ans[v]) continue;
			ans[v] = 2;
			q.PB(v);
			Y--;
			if (Y == 0) break;
		}
	}
	//1 -> inds.fi
	//2 -> inds.se
	//0 -> 3 - inds.fi - inds.se
	FOR(i, 0, N)
	{
		if (ans[i] == 0)
		{
			ans[i] = 3 - inds.fi - inds.se;
		}
		else if (ans[i] == 1)
		{
			ans[i] = inds.fi;
		}
		else if (ans[i] == 2)
		{
			ans[i] = inds.se;
		}
	}
	return ans;
}

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