Submission #892085

#	Time	Username	Problem	Language	Result	Execution time	Memory
892085		Doncho_Bonboncho	Race (IOI11_race)	C++17	0 / 100	2 ms	7512 KiB

race

#include <bits/stdc++.h>
using namespace std;

template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; }

#ifndef LOCAL
#define cerr if( false )cerr
#endif

#define out(x) #x << " = " << x << "  "

typedef long long ll;

const int MAX_N = 1e5 + 42;
const ll mod = 1e9 + 7;

int n, k;
std::vector< std::pair< int , int >> v[MAX_N];
int l[MAX_N];

bool viz[MAX_N];
int sz[MAX_N];

void dfs( int x, int par = -1 ){
	sz[x] = 1;
	for( auto J : v[x] ){
		int j = J.first;
		if( j == par || viz[j] ) continue;
		dfs( j, x );
		sz[x] += sz[j];
	}
}
int centroid( int x, int SZ, int par = -1 ){
	for( auto J : v[x] ){
		int j = J.first;
		if( j == par || viz[j] ) continue;
		if( sz[j] > ( SZ / 2 ) ) return centroid( j, SZ, x );
	}
	return x;
}

std::unordered_map< int , int >m;
ll nas = mod;
void findNas( int x, bool type, int len, int par = -1, int d = 1 ){

	auto pos = m.find( k - len );
	if( type ){
		if( pos != m.end() ){
			chkmin( nas, d + pos->second );
		}
	}else m[len] = d;

	for( auto J : v[x] ){
		int j = J.first;
		if( j == par || viz[j] ) continue;
		findNas( j, type, len + J.second, x, d + 1 );
	}

}

void centDecomp( int x, int par = -1 ){

	dfs( x );
	int c = centroid( x, sz[x] );
	viz[c] = true;

	m[0] = 0;
	for( auto J : v[c] ){
		int j = J.first;
		if( viz[j] ) continue;
		findNas( j, true , J.second);
		findNas( j, false, J.second );
	}

	m.clear();

	for( auto J : v[c] ){
		int j = J.first;
		if( viz[j] ) continue;
		centDecomp( j, c );
	}
}


int best_path(int N, int K, int H[][2], int L[]) {

	n = N;
	k = K;

	for( int i=0 ; i < n-1 ; i ++ ){
		int a = H[i][0];
		int b = H[i][1];
		v[a].push_back({ b, L[i] });
		v[b].push_back({ a, L[i] });
	}

	centDecomp( 0 );

	if( nas == mod ) nas = -1;
	return nas;
}

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