Submission #292330

#	Time	Username	Problem	Language	Result	Execution time	Memory
292330		Lawliet	Fun Tour (APIO20_fun)	C++17	100 / 100	414 ms	20024 KiB

fun

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

using namespace std;

const int MAXN = 200010;

int n;

int depth[MAXN];

vector<int> adj;
vector<int> groups[5];

bool cmp(int i, int j) { return depth[i] < depth[j]; }

bool hasMajoritary()
{
	int mx = 0;
	int sum = 0;

	for(int i = 0 ; i < 3 ; i++)
	{
		sum += (int)groups[i].size();
		mx = max( mx , (int)groups[i].size() );
	}

	return ( sum - mx <= mx );
}

int getCentroid()
{
	int sub = n;
	int cent = 0;

	for(int i = 1 ; i < n ; i++)
	{
		int curSub = attractionsBehind( 0 , i );

		if( curSub > n/2 && curSub < sub )
		{
			cent = i;
			sub = curSub;
		}
	}

	return cent;
}

void findGroups()
{
	int degree = 0;

	for(int i = 0 ; i < n ; i++)
	{
		if( depth[i] == 1 )
		{
			adj.push_back( i );
			groups[degree++].push_back( i );
		}
	}

	for(int i = 0 ; i < n ; i++)
	{
		if( depth[i] <= 1 ) continue;

		int distA = hoursRequired( i , adj[0] );
		int distB = hoursRequired( i , adj[1] );

		if( distA < distB ) groups[0].push_back( i );
		if( distA > distB ) groups[1].push_back( i );
		if( distA == distB ) groups[2].push_back( i );
	}

	for(int i = 0 ; i < degree ; i++)
		sort( groups[i].begin() , groups[i].end() , cmp );
}

int getMajoritary()
{
	int maj = 0;

	for(int i = 0 ; i < 3 ; i++)
		if( (int)groups[maj].size() <= (int)groups[i].size() ) maj = i;

	return maj;
}

vector<int> createFunTour(int N, int Q) 
{
	n = N;

	if( N == 2 )
	{
		vector<int> ans = { 0 , 1 };
		return ans;
	}

	int cent = getCentroid();

	depth[cent] = 0;

	for(int i = 0 ; i < N ; i++)
		if( i != cent ) depth[i] = hoursRequired( cent , i );

	findGroups();

	int first = 0;
	vector<int> ans;

	int last = -1;

	while( !hasMajoritary() )
	{
		int nxt = 0;
		if( last == 0 ) nxt = 1;

		for(int i = 0 ; i < 3 ; i++)
		{
			if( last == i ) continue;

			if( depth[ groups[nxt].back() ] <= depth[ groups[i].back() ] )
				nxt = i;
		}

		last = nxt;

		ans.push_back( groups[nxt].back() );
		groups[nxt].pop_back();
	}

	int indMajoritary = getMajoritary();

	if( last != -1 )
	{
		int otherGroup = 3 - last - indMajoritary;

		if( depth[ ans.back() ] <= depth[ groups[otherGroup].back() ] ) 
			first = 1;
	}

	if( indMajoritary != 0 )
		swap( groups[0] , groups[indMajoritary] );

	while( !groups[2].empty() )
	{
		groups[1].push_back( groups[2].back() );
		groups[2].pop_back();
	}

	sort( groups[1].begin() , groups[1].end() , cmp );

	for(int i = 1 ; i <= 3*N ; i++)
	{
		if( !groups[first].empty() )
		{
			ans.push_back( groups[first].back() );
			groups[first].pop_back();
		}

		if( !groups[1 - first].empty() )
		{
			ans.push_back( groups[1 - first].back() );
			groups[1 - first].pop_back();
		}
	}

	ans.push_back( cent );
	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34