Submission #96994

#	Time	Username	Problem	Language	Result	Execution time	Memory
96994		tugushka	Race (IOI11_race)	C++14	100 / 100	2054 ms	40752 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;

using pii = pair < int, int >;

map < int, int > x, y;
vector < vector < pair < int, int > > > to;
int n, k, sz[N], res = 1e9;
bool blocked[N];

int get_size(int u, int p){
	sz[u] = 1;
	for( pii v : to[u] ){
		if( blocked[v.first] || v.first == p ) continue;
		sz[u] += get_size( v.first, u );
	}
	return sz[u];
}

int get_center( int u, int p, int comp_size ){
	for( pii v : to[u] ){
		if( blocked[v.first] || v.first == p ) continue;
		if( sz[v.first] > comp_size ) return get_center(v.first, u, comp_size);
	}
	return u;
}

void dfs(int u, int p, int len, int dis){
	if( y.find( len ) == y.end() ) y[len] = dis;
	else{
		y[len] = min( dis, y[len] );
	}

	for( pii v : to[u] ){
		if( blocked[v.first] || v.first == p ) continue;
		dfs( v.first, u, len + v.second, dis + 1 );
	}
}

void decomp(int u){
	u = get_center(u, -1, 2*get_size(u, -1)/3);

	x.clear();
	x[0] = 0;
	for( pii v : to[u] ){
		if( blocked[v.first] ) continue;
		y.clear();
		dfs( v.first, u, v.second, 1 );
		for( pii now : y ){
			if( x.find( k-now.first ) != x.end() ){
				res = min( res, x[k-now.first] + now.second );
			}
		}

		for( pii now : y ){
			if( x.find( now.first ) == x.end() ) x[now.first] = now.second;
			else{
				x[now.first] = min( x[now.first], now.second );
			}
		}
	}

	blocked[u] = 1;
	for( pii v : to[u] ){
		if( blocked[v.first] ) continue;
		decomp( v.first );
	}

}

int best_path(int NN, int K, int H[][2], int L[]){
	n = NN, k = K;
	to.resize(n);
	for(int i = 0 ; i < n-1 ; i++){
		to[ H[i][0] ].push_back( make_pair( H[i][1], L[i] ) );
		to[ H[i][1] ].push_back( make_pair( H[i][0], L[i] ) );
	}

	decomp( 0 );

	return res == 1e9 ? -1 : res;
}

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