Submission #919039

#	Time	Username	Problem	Language	Result	Execution time	Memory
919039		Cutebol	Race (IOI11_race)	C++17	21 / 100	317 ms	16228 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] , mx ;
bool vis[Ne] ;
vector <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 ;
	chmin ( ans , d+mp[k-s] ) ;
	chmax ( mx , s ) ;
	for ( auto to : g[v] ) if ( to.ff != p && !vis[to.ff] ) dfs( to.ff , d+1 , s+to.ss , v , i ) ;
}
void upd( int v , int d , int s , int p , int i ){
	if ( s > k ) return ;
	chmin ( mp[s] , d ) ;
	for ( auto to : g[v] ) if ( to.ff != p && !vis[to.ff] ) upd( to.ff , d+1 , s+to.ss , v , i ) ;
}

void go ( int v ){
	v = centroid( v , fsz(v)/2 ) ;
	vis[v] = 1 ; mx = 0 ;
	for ( auto to : g[v] ){
		dfs ( to.ff , 1 , to.ss , -1 , to.ff ) ;
		upd ( to.ff , 1 , to.ss , -1 , to.ff ) ;
	}
	for ( int i = 0 ; i <= mx ; i ++ ) mp[i] = INT_MAX - n ;
	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 ;
	mp.resize(k+1 , INT_MAX-n);
	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: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57