제출 #596221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596221		AriaH	Split the Attractions (IOI19_split)	C++17	40 / 100	389 ms	101976 KiB

split

#include "split.h"
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

vector < int > ret;

set < int > G[N];

int n, m, a, b, c, par[N], sz[N], Can, mark[N], sub[N];

vector < pii > Del, extra[N];

int pre(int v, int P)
{
	int ret = v;
	mark[v] = 1;
	sub[v] = 1;
	vector < int > del;
	for(auto u : G[v])
	{
		if(u == P) continue;
		if(mark[u])
		{
			del.push_back(u);
			continue;
		}
		int nxt = pre(u, v);
		if(sub[u] * 2 > n) ret = nxt;
		sub[v] += sub[u];
	}
	for(auto x : del)
	{
		if(G[v].find(x) != G[v].end())
		{
			Del.push_back(Mp(x, v));
			G[v].erase(x);
		}
	}
	return ret;
}

void solve(int v, int P, int jad)
{
	par[v] = jad;
	sz[jad] ++;
	for(auto u : G[v])
	{
		if(u == P) continue;
		solve(u, v, jad);
	}
}

set < pii > st;

int calc(int x)
{
	if(x == a) return 1;
	if(x == b) return 2;
	return 3;
}

int get(int x)
{
	return (x == par[x]? x : par[x] = get(par[x]));
}

int unify(int v, int u)
{
	pii late = Mp(v, u);
	v = get(v), u = get(u);
	if(v == u) return 0;
	sz[v] += sz[u];
	par[u] = v;
	if(SZ(extra[v]) < SZ(extra[u]))
	{
		extra[v].swap(extra[u]);
	}
	for(auto now : extra[u])
	{
		extra[v].push_back(now);
	}
	extra[u].clear();
	extra[v].push_back(late);
	return 1;
}

vector < int > find_split(int _n, int _a, int _b, int _c, vector < int > p, vector < int > q)
{
	n = _n;
	a = _a;
	b = _b;
	c = _c;
	m = SZ(p);
	for(int i = 0; i < m; i ++)
	{
		p[i] ++, q[i] ++;
		G[p[i]].insert(q[i]);
		G[q[i]].insert(p[i]);
	}
	int cen = pre(1, 0);
	memset(mark, 0, sizeof mark);
	pre(cen, 0);
	for(auto u : G[cen])
	{
		solve(u, cen, u);
	}
	sz[cen] = 1;
	par[cen] = cen;
	int id = 0;
	for(auto u : G[cen])
	{
		if(sub[u] > sub[id]) id = u;
	}
	int Mn = min({a, b, c});
	ret.resize(n, 0);
	assert(id != 0);
	for(auto [x, y] : Del)
	{
		if(sz[id] >= Mn) break;
		if(unify(x, y))
		{
			id = get(id);
			if(sz[get(x)] > sz[id])
			{
				id = get(x);
			}
		}
	}
	if(sz[id] < Mn)
	{
		return ret;
	}
	for(int i = 1; i <= n; i ++)
	{
		if(get(i) == id)
		{
			if(G[i].find(cen) != G[i].end())
			{
				G[i].erase(cen);
				G[cen].erase(i);
			}
		}
	}
	for(auto [x, y] : extra[id])
	{
		G[x].insert(y);
		G[y].insert(x);
	}
	int col = calc(Mn);
	for(int i = 1; i <= n; i ++)
	{
		if(i == cen) continue;
		if(get(i) == id)
		{
			st.insert(Mp(SZ(G[i]), i));
			ret[i - 1] = col;
		}
	}
	while(SZ(st) > Mn)
	{
		int node = st.begin()->S;
		st.erase(st.begin());
		ret[node - 1] = 0;
		for(auto u : G[node])
		{
			st.erase(Mp(SZ(G[u]), u));
			G[u].erase(node);
			st.insert(Mp(SZ(G[u]), u));
		}
		G[node].clear();
	}
	int Mn2 = a + b + c - Mn - max({a, b, c});
	assert(Mn2 <= (n - sz[id]));
	int col2 = -1;
	if(a == Mn2 && col != 1) { col2 = 1; }
	else if(b == Mn2 && col != 2) { col2 = 2; }
	else if(c == Mn2 && col != 3) { col2 = 3; }
	assert(col2 != -1);
	st.clear();
	for(int i = 1; i <= n; i ++)
	{
		if(get(i) != id)
		{
			st.insert(Mp(SZ(G[i]), i));
			ret[i - 1] = col2;
		}
	}
	while(SZ(st) > Mn2)
	{
		int node = st.begin()->S;
		st.erase(st.begin());
		ret[node - 1] = 0;
		for(auto u : G[node])
		{
			st.erase(Mp(SZ(G[u]), u));
			G[u].erase(node);
			st.insert(Mp(SZ(G[u]), u));
		}
		G[node].clear();
	}
	for(int i = 0; i < n; i ++)
	{
		if(ret[i] == 0)
		{
			ret[i] = 1 + 2 + 3 - col - col2;
		}
	}
	return ret;
}

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