Submission #290559

#	Time	Username	Problem	Language	Result	Execution time	Memory
290559		Lawliet	Swapping Cities (APIO20_swap)	C++17	100 / 100	295 ms	21496 KiB

swap

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

using namespace std;

const int MAXN = 200010;
const int INF = 1000000010;

int n, m;

int w[MAXN];
int ord[MAXN];
int minTime[MAXN];
int anc[MAXN], tW[MAXN], degree[MAXN];

vector<int> nodes[MAXN];

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

int find(int cur)
{
	if( anc[cur] == cur ) return cur;
	return find( anc[cur] );
}

void update(int i, int curW)
{
	if( curW == INF ) return;
	if( minTime[i] != INF ) return;

	for(int k = 0 ; k < (int)nodes[i].size() ; k++)
		minTime[ nodes[i][k] ] = curW;
}

void join(int i, int j, int curW)
{
	degree[i]++; degree[j]++;
	bool flip = ( degree[i] >= 3 || degree[j] >= 3 );

	i = find(i), j = find(j);

	if( i == j ) flip = true;

	if( flip )
	{
		update( i , curW );
		update( j , curW );
	}

	if( i == j ) return;

	bool isSpecial = ( minTime[i] != INF || minTime[j] != INF );

	if( isSpecial )
	{
		update( i , curW );
		update( j , curW );
	}

	if( (int)nodes[i].size() < (int)nodes[j].size() )
		swap( i , j );

	anc[j] = i;
	tW[j] = curW;

	while( !nodes[j].empty() )
	{
		nodes[i].push_back( nodes[j].back() );
		nodes[j].pop_back();
	}
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) 
{
	n = N; m = M;

	for(int i = 0 ; i < n ; i++)
	{
		anc[i] = i;
		nodes[i].push_back( i );

		minTime[i] = tW[i] = INF;
	}

	for(int i = 0 ; i < m ; i++)
		w[i] = W[i];

	iota( ord , ord + m , 0 );
	sort( ord , ord + m , cmp );

	for(int i = 0 ; i < m ; i++)
		join( U[ ord[i] ] , V[ ord[i] ] , W[ ord[i] ] );
}

int getMinimumFuelCapacity(int X, int Y) 
{
	if( minTime[X] == INF ) return -1;

	int ans = minTime[X];

	while( X != Y )
	{
		if( tW[X] > tW[Y] )
			swap( X , Y );

		ans = max( ans , tW[X] );
		X = anc[X];
	}

	return ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27