제출 #918824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918824		Cutebol	경주 (Race) (IOI11_race)	C++17	0 / 100	2 ms	8792 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std ;
#define ff first 
#define ss second

const int Ne = 2e5 + 5 ;
const int inf = 1e9 ;

template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

int n , k , ans = inf , sz[Ne] ;
bool vis[Ne] ;
map <int , int> mp ;
vector <pair <int , int>> g[Ne] ;
vector <pair <int , int>> vec ;

int fsz ( int v , int p = -1 ){
	sz[v] = 1 ;
	for ( auto to : g[v] ){
		if ( to.ff != p && !vis[to.ff] ) fsz(to.ff,v) , sz[v] += sz[to.ff] ;
	} return sz[v] ;
}

int centroid ( int v , int s , int p = -1 ){
	for ( auto to : g[v] ){
		if ( sz[to.ff] >= s && to.ff != p && !vis[to.ff] ) return centroid( to.ff , s , v ) ;
	} return v ;
}

void dfs( int v , int d , int s , int p , int i ){
	if ( s > k ) return ;
	if ( mp.count(mp[k-s]) )chmin ( ans , d+mp[k-s] ) ;
	vec.push_back({d,s}) ;
	for ( auto to : g[v] ) if ( to.ff != p && !vis[to.ff] ) dfs( to.ff , d+1 , s+to.ss , v , i ) ;
}

void go ( int v ){
	v = centroid( v , fsz(v)/2 ) ;
	vis[v] = 1 ;
	mp.clear() ;
	for ( auto to : g[v] ){
		dfs ( to.ff , 1 , to.ss , -1 , to.ff ) ;
		for ( auto i : vec ){
			if ( !mp.count(i.ss) ) mp[i.ss] = i.ff ;
			chmin ( mp[i.ss] , i.ff ) ;
		} vec.clear() ;
	} 
	if ( mp.count(k) ) chmin ( ans , mp[k] ) ;
	for ( auto to : g[v] ) if ( !vis[to.ff] ) go (to.ff) ;
}

int best_path(int N, int K, int h[][2], int l[]){
	n = N , k = K ;
	for ( int i = 0 ; i < n-1 ; i ++ ){
		g[h[i][0]].push_back({h[i][1],l[i]}) ;
		g[h[i][1]].push_back({h[i][0],l[i]}) ;
	}
	go(1) ;
	return (ans == inf) ? -1 : ans ;
}

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