Submission #870832

#	Time	Username	Problem	Language	Result	Execution time	Memory
870832		NintsiChkhaidze	Race (IOI11_race)	C++17	100 / 100	833 ms	46008 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int NN = 2e5 + 5;
vector <pair <int,int> > v[NN];
int k,ans,vis[NN];
map <int,int> mp;

int findcentroid(int x,int par,int n,int &centroid){
	int s=1;
	for (auto [to,w]: v[x]){
		if (!vis[to] && to != par) 
			s += findcentroid(to,x,n,centroid);
	}
	
	if (centroid == -1 && (par == -1 || s*2 >= n)) centroid = x;
	return s;
}

void dfs(int x,int par,int dist,int dep,int type){
	
	if (dist == k){
		ans = min(ans,dep);
		return;
	}
	
	if (!type){
		if (mp.find(k - dist) != mp.end()){
			ans=min(ans,mp[k - dist] + dep);
		}
	}else{
		if (mp.find(dist) == mp.end()){
			mp[dist] = dep;
		}else{
			mp[dist] = min(mp[dist],dep);
		}
	}
	
	for (auto [to,w]: v[x]){
		if (!vis[to] && to != par) dfs(to,x,w + dist,dep + 1,type);
	}
}
void solve(int x,int n){
	int centroid = -1;
	findcentroid(x,-1,n,centroid);
	vis[centroid] = 1;
	mp.clear();
	
	for (auto [to,w]: v[centroid]){
		if (!vis[to]){
			dfs(to,x,w,1,0);
			dfs(to,x,w,1,1);
		}
	}
	
	for (auto [to,w]: v[centroid]){
		if (!vis[to]) solve(to,n/2);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
    
  	for (int i = 0; i < N - 1; i++){
  		int a = H[i][0] + 1,b = H[i][1] + 1;
  		v[a].pb({b,L[i]});
  		v[b].pb({a,L[i]});
  	}
	k=K;
	ans=1e9;
	solve(1,N);
	if (ans == 1e9) ans=-1;
	return ans; 
}

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