제출 #143951

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

split

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 100005;

int N, M, sz[MAXN], parent[MAXN], total[MAXN], centroid, component[MAXN], sum;
vi MST[MAXN], Graph[MAXN], ans, TP;
vector<pii> part ( 3, {0, 0} );

int look ( int node )
{
	if ( parent[node] == node )
		return node;
	return parent[node] = look ( parent[node] );
}

void join ( int nodeA, int nodeB )
{
	parent[look(nodeB)] = look(nodeA);
}

void pre ( int node, int p = -1 )
{
	sz[node] = 1;
	for ( auto i : MST[node] )
		if ( i != p )
			pre ( i, node ), sz[node] += sz[i];
}

int find_centroid ( int node, int p = -1 )
{
	for ( auto i : MST[node] )
		if ( i != p && 2*sz[i] > sz[0] )
			return find_centroid ( i, node );
	return node;
}

void paint ( int node, int p, int color )
{
	if ( ans[node] )
		return;

	if ( part[color].first )
	{
		part[color].first--;
		ans[node] = part[color].second;
	}
	else
		ans[node] = part[2].second;
	
	for ( auto i : MST[node] )
		if ( i != p )
			paint ( i, node, color );
}

void compress ( int root, int node, int p )
{
	component[node] = root;
	for ( auto i : MST[node] )
		if ( i != p )
			compress ( root, i, node );
}

void check ( int node, int p = -1 )
{
	sum += sz[node];
	TP.push_back ( node );
	if ( sum >= part[0].first )
		return;
	
	for ( auto i : Graph[node] )
		if ( i != p )
			check ( i, node );
}

vi find_split ( int _n, int a, int b, int c, vi p, vi q )
{
	part[0] = {a, 1};
	part[1] = {b, 2};
	part[2] = {c, 3};
	sort ( part.begin(), part.end() );
	N = _n;
	M = p.size();
	ans.resize ( N );
	
	for ( int i = 0; i < N; i++ )
		parent[i] = i;
	for ( int i = 0; i < M; i++ )
	{
		if ( look ( p[i] ) != look ( q[i] ) )
		{
			MST[p[i]].push_back ( q[i] );
			MST[q[i]].push_back ( p[i] );
			join ( p[i], q[i] );
		}
	}
	
	pre ( 0 );
	centroid = find_centroid ( 0 );
	pre ( centroid );
	
	component[centroid] = centroid;
	for ( auto i : MST[centroid] )
	{
		if ( sz[i] >= part[0].first )
		{
			paint ( i, centroid, 0 );
			paint ( centroid, -1, 1 );
			return ans;
		}
		
		compress ( i, i, centroid );
	}
	
	for ( int i = 0; i < N; i++ )
		parent[i] = i;
	for ( int i = 0; i < M; i++ )
	{
		if ( p[i] == centroid or q[i] == centroid )
			continue;

		if ( look ( component[p[i]] ) != look ( component[q[i]] ) )
		{
			join ( component[p[i]], component[q[i]] );
			Graph[component[p[i]]].push_back ( component[q[i]] );
			Graph[component[q[i]]].push_back ( component[p[i]] );
		}
	}
	
	for ( auto i : MST[centroid] )
	{
		sum = 0;
		check ( i );
		if ( sum >= part[0].first )
		{
			for ( auto j : TP )
				paint ( j, centroid, 0 );
			paint ( centroid, -1, 1 );
			return ans;
		}
	}
	for ( auto &i : ans )
		i = 0;
	return ans;
}

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