Submission #838358

#	Time	Username	Problem	Language	Result	Execution time	Memory
838358		MohamedAhmed04	Race (IOI11_race)	C++14	100 / 100	423 ms	56480 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std ;

const int MAX = 1e6 + 10 ;

vector< vector< pair<int , int> > >adj(MAX) ;
int n , k ;

int src ;
int sz[MAX] , mark[MAX] ;

void pre_dfs(int node , int par)
{
	sz[node] = 1 ;
	for(auto &childd : adj[node])
	{
		int child = childd.first , w = childd.second ;
		if(child == par || mark[child])
			continue ;
		pre_dfs(child , node) ;
		sz[node] += sz[child] ;
	}
}

int FindCentroid(int node , int par)
{
	for(auto &childd : adj[node])
	{
		int child = childd.first , w = childd.second ;
		if(child == par || mark[child])
			continue ;
		if(sz[child] > sz[src] / 2)
			return FindCentroid(child , node) ;
	}
	return node ;
}

int ans = 1e9 ;
int val[MAX] , dep[MAX] ;

void dfs(int node , int par , int w , int t)
{
	w = min(w , k+1) ;
	if(t == 0 && w <= k)
		ans = min(ans , val[k-w] + dep[node]) ;
	else if(t == 1 && w <= k)
		val[w] = min(val[w] , dep[node]) ;
	else if(t == 2 && w <= k)
		val[w] = 1e9 ;
	for(auto &childd : adj[node])
	{
		int child = childd.first , w2 = childd.second ;
		if(mark[child] || child == par)
			continue ;
		dep[child] = dep[node] + 1 ;
		dfs(child , node , w + w2 , t) ;
	}
}

void solve(int Src)
{
	src = Src ;
	pre_dfs(src , -1) ;
	int centroid = FindCentroid(src , -1) ;
	mark[centroid] = 1 ;
	dep[centroid] = 0 , val[0] = 0 ;
	for(auto &childd : adj[centroid])
	{
		int child = childd.first , w = childd.second ;
		if(mark[child])
			continue ;
		dep[child] = 1 ;
		dfs(child , centroid , w , 0) ;
		dfs(child , centroid , w , 1) ;
	}
	for(auto &childd : adj[centroid])
	{
		int child = childd.first , w = childd.second ;
		if(mark[child])
			continue ;
		dfs(child , centroid , w , 2) ;
	}
	for(auto &childd : adj[centroid])
	{
		int child = childd.first , w = childd.second ;
		if(mark[child])
			continue ;
		solve(child) ;
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N , k = K ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		adj[H[i][0]+1].emplace_back(H[i][1]+1 , L[i]) ;
		adj[H[i][1]+1].emplace_back(H[i][0]+1 , L[i]) ;
	}
	for(int i = 0 ; i <= k ; ++i)
		val[i] = 1e9 ;
	solve(1) ;
	if(ans == 1e9)
		ans = -1 ;
	return ans ;
}

Compilation message (stderr)

race.cpp: In function 'void pre_dfs(int, int)':
race.cpp:19:30: warning: unused variable 'w' [-Wunused-variable]
   19 |   int child = childd.first , w = childd.second ;
      |                              ^
race.cpp: In function 'int FindCentroid(int, int)':
race.cpp:31:30: warning: unused variable 'w' [-Wunused-variable]
   31 |   int child = childd.first , w = childd.second ;
      |                              ^
race.cpp: In function 'void solve(int)':
race.cpp:87:30: warning: unused variable 'w' [-Wunused-variable]
   87 |   int child = childd.first , w = childd.second ;
      |                              ^

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