# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
758582 | KN200711 | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;
set< pair<ll, int> > nw[200001];
vector< pair<ll, int> > edge[200001];
int ans = 1e9 + 11;
int KK;
void dfs(int a, int pr, ll v, int c) {
nw[a].insert(make_pair(v, c));
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
dfs(edge[a][k].fi, a, v + edge[a][k].se, c+1);
if(nw[edge[a][k].fi].size() > nw[a].size()) swap(nw[a], nw[edge[a][k].fi]);
for(auto p : nw[edge[a][k].fi]) {
auto it = nw[a].lower_bound(make_pair(K + 2ll * v - p.fi + 1, 0));
if(it == nw[a].begin()) continue;
it--;
if(it->fi == K - v) ans = min(ans, it->se + p.se - 2 * c);
}
for(auto p : nw[edge[a][k].fi]) {
nw[a].insert(p);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
KK = K;
for(int i=0;i<N;i++) edge[i].clear();
for(int i=0;i<N-1;i++) {
edge[H[i][0]].push_back(make_pair(H[i][1], L[i]));
edge[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
ans = 1e9 + 11;
dfs(0, -1, 0, 0);
if(ans == 1e9 + 11) return -1;
return ans;
}