제출 #892090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892090		Doncho_Bonboncho	경주 (Race) (IOI11_race)	C++17	21 / 100	3011 ms	66752 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 , 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{
		auto pos2 = m.find( len );
		if( pos2 == m.end() || pos2->second > d ) 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 ){

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

	m.clear();
	m[0] = 0;

	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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57