Submission #838355

#	Time	Username	Problem	Language	Result	Execution time	Memory
838355		MohamedAhmed04	Race (IOI11_race)	C++14	0 / 100	3 ms	4948 KiB

race

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

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds ;

template<class T> using ordered_set = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 2e5 + 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 , bool t)
{
	w = min(w , k+1) ;
	if((!t) && w <= k)
		ans = min(ans , val[k-w] + dep[node]) ;
	else if(t && w <= k)
		val[w] = min(val[w] , dep[node]) ;
	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 ;
	for(int i = 0 ; i <= sz[src]+1 ; ++i)
		val[i] = 1e9 ;
	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 ;
		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]) ;
	}
	solve(1) ;
	if(ans == 1e9)
		ans = -1 ;
	return ans ;
}

Compilation message (stderr)

race.cpp: In function 'void pre_dfs(int, int)':
race.cpp:26:30: warning: unused variable 'w' [-Wunused-variable]
   26 |   int child = childd.first , w = childd.second ;
      |                              ^
race.cpp: In function 'int FindCentroid(int, int)':
race.cpp:38:30: warning: unused variable 'w' [-Wunused-variable]
   38 |   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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57