제출 #918642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918642		Cutebol	경주 (Race) (IOI11_race)	C++17	31 / 100	3082 ms	32856 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] ;
vector< vector<pair <int , int>>> mp ;
vector <pair <int , int>> g[Ne] ;

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 ;
	for ( auto j : mp[k-s] ) if ( j.ss != i ) chmin ( ans , j.ff+d ) ;
	mp[s].push_back({d,i}) ;
	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() ; mp.resize(k+2) ;
	for ( auto to : g[v] ){
		dfs ( to.ff , 1 , to.ss , -1 , to.ff ) ;
	} for ( auto i : mp[k] ) chmin ( ans , i.ff ) ;
	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: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57