Submission #1131667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131667		vako_p	Race (IOI11_race)	C++20	100 / 100	275 ms	77480 KiB

race

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

const int mxN = 2e5 + 5;
ll n,k,anss = 1e9,dis[mxN],d[mxN];
vector<pair<ll,ll>> v[mxN];
set<pair<ll,ll>> s[mxN]; 

void dfs(ll at, ll par){
	s[at].insert({dis[at], d[at]});
	for(auto it : v[at]){
		if(it.first == par) continue;
		d[it.first] = d[at] + 1;
		dis[it.first] = dis[at] + it.second;
		dfs(it.first, at);
	}
	for(auto it1 : v[at]){
		ll it = it1.first;
		if(it == par) continue;
		if(s[at].size() < s[it].size()) swap(s[at], s[it]);
		for(auto x : s[it]){
			auto mn = s[at].lower_bound({dis[at] * 2 + k - x.first, 0LL});
			if(mn == s[at].end()) continue;
			pair<ll,ll> num = *mn;
			if(num.first != dis[at] * 2 + k - x.first) continue;
			anss = min(anss, x.second - 2 * d[at] + num.second);
		}
		for(auto x : s[it]) s[at].insert(x);
		s[it].clear();
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N; k = K;
	for(int i = 0; i < n - 1; i++){
		v[H[i][0]].pb({H[i][1], L[i]});
		v[H[i][1]].pb({H[i][0], L[i]});		
	}
	dfs(1, 1);
	if(anss == 1e9) return -1;
	return anss;
}						

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