Submission #892091

#	Time	Username	Problem	Language	Result	Execution time	Memory
892091		Doncho_Bonboncho	Race (IOI11_race)	C++17	0 / 100	6 ms	27992 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 = 1e6 + 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 ){
	cerr << out( x ) << out( par ) << endl;
	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 ){
	cerr << out( x ) << out( SZ )  << endl;
	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 , std::pair< int, int > >m;
ll nas = mod;
int tt;
void findNas( int x, bool type, int len, int par = -1, int d = 1 ){

	auto pos = m.find( k - len );
	if( pos != m.end() and ( pos->second.second < tt ) ) m.erase( pos );

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

	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 ){

	cerr << out( x ) << endl;
	dfs( x );

	int c = centroid( x, sz[x] );
	cerr << out( c ) << endl;
	viz[c] = true;

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

	tt ++;

	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] });
	}

	m[0] = { 0, mod };

	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