제출 #1171997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171997		dpsaveslives	Split the Attractions (IOI19_split)	C++20	100 / 100	77 ms	24252 KiB

split

#include<bits/stdc++.h>
#include "split.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int INF = 1e9;
const int MX = 1e5+5;

vector<in> edges;
vector<int> adj_G[MX];
vector<int> adj_T[MX];
vector<bool> vis;
vector<int> sub;

void dfs(int u)
{
	vis[u] = 1;
	for(int v: adj_G[u])
	{
		if(vis[v])
			continue;
		adj_T[u].pb(v);
		adj_T[v].pb(u);
		dfs(v);
		sub[u]+=sub[v];
	}
	return;
}

int centroid(int u, int p, int sz)
{
	for(int v: adj_T[u])
	{
		if(v==p) continue;
		if(2*sub[v] >= sz)
			return centroid(v, u, sz);
	}
	return u;
}

vector<int> pa;

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

int merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u == v)
		return 0;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	pa[u] = v;
	return -pa[v];
}

int rep(int u, int p)
{
	int ret = 1;
	for(int v: adj_T[u])
	{
		if(v==p) continue;
		merge(u, v);
		ret+=rep(v, u);
	}
	return ret;
}

vector<bool> SPLIT;

void perform(int u, bool typ, int cnt, int val, vector<int> &ans, int &cur)
{
	/*cout << "size restriction to " << cnt << endl;
	cout << "reached cur = " << cur << endl;*/
	vis[u] = 1;
	ans[u] = val;
	cur++;
	if(cur == cnt)
		return;
	for(int v: adj_G[u])
	{
		if(vis[v]) continue;
		if(SPLIT[v] != typ) continue;
		perform(v, typ, cnt, val, ans, cur);
		if(cur == cnt)
			return;
	}
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	vector<in> pp = {{a, 1}, {b, 2}, {c, 3}};
	sort(pp.begin(), pp.end());


	vector<int> ans(n, 0);
	edges.clear();
	for(int i = 0; i < n; i++)
	{
		adj_G[i].clear();
		adj_T[i].clear();
	}
	int m = p.size();
	for(int i = 0; i < m; i++)
	{
		edges.pb({p[i], q[i]});
		adj_G[p[i]].pb(q[i]);
		adj_G[q[i]].pb(p[i]);
	}
	sub.assign(n, 1);
	vis.assign(n, 0);
	dfs(0);
	int x = centroid(0, -1, n);
	pa.assign(n, -1);
	SPLIT.assign(n, 0);
	bool win = 0;
	for(int z: adj_T[x])
	{
		if(win)
			continue;
		int s = rep(z, x);
		if(s >= pp[0][0])
		{
			win = 1;
			for(int i = 0; i < n; i++)
				SPLIT[i] = (leader(i) != leader(z));
		}
	}
	for(auto [xp, y]: edges)
	{
		if((xp == x) || (y == x))
			continue;
		int D = merge(xp, y);
		if(D >= pp[0][0])
		{
			win = 1;
			for(int i = 0; i < n; i++)
				SPLIT[i] = (leader(i) != leader(y))^(((2*D) >= n));
			break;
		}
	}
	if(!win)
		return ans;
	for(int k = 0; k < 2; k++)
	{
		int j = 0;
		while(SPLIT[j] != k)
			j++;
		vis.assign(n, 0);
		int help = 0;
		perform(j, k&1, pp[k][0], pp[k][1], ans, help);
	}
	for(int i = 0; i < n; i++)
	{
		if(ans[i]) continue;
		ans[i] = pp[2][1];
	}
	return ans;
}

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