Submission #77379

#	Time	Username	Problem	Language	Result	Execution time	Memory
77379		joseacaz	Race (IOI11_race)	C++17	100 / 100	720 ms	65868 KiB

race

#include "race.h"
#include <vector>
#define MAXN 200005
#define MAXK 1000005
#define pii pair < int, int >
#define mp make_pair

using namespace std;

int C, K, tam[MAXN], dead[MAXN], tim[MAXK], arr[MAXK];
vector < pii > Graph[MAXN];

void pre_tam ( int node, int parent )
{
	tam[node] = 1;
	for ( auto i : Graph[node] )
		if ( i.first != parent && !dead[i.first] )
			pre_tam ( i.first, node ), tam[node] += tam[i.first];
}

int find_centroid ( int node, int parent, int siz )
{
	for ( auto i : Graph[node] )
		if ( i.first != parent && 2 * tam[i.first] > siz && !dead[i.first] )
			return find_centroid ( i.first, node, siz );
	return node;
}

int qry ( int node, int parent, int s, int a )
{
	if ( s > K )
		return (1 << 30);

	int ret = (1<<30);
	if ( tim[K - s] == C )
		ret = arr[K - s] + a;

	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != parent )
			ret = min ( qry ( i.first, node, s + i.second, a + 1 ), ret );

	return ret;
}

void upd ( int node, int parent, int s, int a )
{
	if ( s > K )
		return;

	if ( tim[s] != C )
	{
		arr[s] = a;
		tim[s] = C;
	}
	else
		arr[s] = min ( arr[s], a );

	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != parent )
			upd ( i.first, node, s + i.second, a + 1 );
}

int solve ( int node )
{
	pre_tam ( node, -1 );
	node = find_centroid ( node, -1, tam[node] );

	C++;
	tim[0] = C;
	arr[0] = 0;

	int ans = (1<<30);
	for ( auto i : Graph[node] )
	{
		if ( !dead[i.first] )
		{
			ans = min ( qry ( i.first, node, i.second, 1 ), ans );
			upd ( i.first, node, i.second, 1 );
		}
	}

	dead[node] = 1;
	for ( auto i : Graph[node] )
		if ( !dead[i.first] )
			ans = min ( ans, solve ( i.first ) );
	
	return ans;
}

int best_path ( int N, int _k, int H[][2], int L[] )
{
	K = _k;
	int u, v;
	for ( int i = 0; i < N - 1; i++ )
	{
		u = H[i][0];
		v = H[i][1];

		Graph[u].push_back ( mp ( v, L[i] ) );
		Graph[v].push_back ( mp ( u, L[i] ) );
	}

	int retval = solve ( 0 );
	if ( retval == (1 << 30) )
		return -1;
	return retval;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57