Submission #120223

#	Time	Username	Problem	Language	Result	Execution time	Memory
120223		joseacaz	Race (IOI11_race)	C++17	0 / 100	6 ms	5120 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXK 1000005
#define INF (1 << 30)

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

int N, K, H[MAXN][2], L[MAXN], dead[MAXN], sz[MAXN], DP[MAXK], vis[MAXK];
vector < pii > Graph[MAXN];

int precalc ( int node, int p = -1 )
{
	sz[node] = 1;
	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != p )
			sz[node] += precalc ( i.first, node );
	return sz[node];
}

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

void cls ( int node, int p )
{
	vis[node] = 0;
	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != p )
			cls ( i.first, node );
}

int qry ( int node, int p, int depth, int cost )
{
	if ( cost > K )
		return INF;

	int aux = INF;
	if ( vis[K - cost] )
		aux = DP[K - cost] + depth;
	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != p )
			aux = min ( aux, qry ( i.first, node, depth + 1, cost + i.second ) );
	return aux;
}

void upd ( int node, int p, int depth, int cost )
{
	if ( cost > K )
		return;

	if ( !vis[cost] )
		DP[cost] = depth;
	vis[cost] = 1;
	DP[cost] = min ( DP[cost], depth );
	for ( auto i : Graph[node] )
		if ( !dead[i.first] && i.first != p )
			upd ( i.first, node, depth + 1, cost + i.second );
}

int solve ( int node )
{
	precalc ( node );
	node = find_centroid ( node, sz[node] );
	dead[node] = 1;

	int aux = INF;
	vis[0] = 1, DP[0] = 0;
	for ( auto i : Graph[node] )
	{
		if ( !dead[i.first] )
		{
			cls ( i.first, node );
			aux = min ( aux, qry ( i.first, node, 1, i.second ) );
			upd ( i.first, node, 1, i.second );
		}
	}

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

	return aux;
}

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

		Graph[H[i][0]].push_back ( {H[i][1], L[i]} );
		Graph[H[i][1]].push_back ( {H[i][0], L[i]} );
	}

	int ans = solve ( 0 );
	return (ans != INF ? ans : -1);
}

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