| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915455 | Julto | 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 <bits/stdc++.h>
#define int long long
using namespace std;
const int mxN = 2e5 + 5, inf = 1e9;
int sz[mxN], cenPar[mxN], dep[mxN], par[mxN][18], sum[mxN];
vector<array<int, 2>> adj[mxN];
vector<array<int, 3>> dists[mxN];
bool done[mxN];
void dfs(int u, int p){
par[u][0] = p;
for(int i = 1; i < 18; i++){
par[u][i] = par[par[u][i - 1]][i - 1];
}
for(auto i : adj[u]){
if(i[0] == p) continue;
dep[i[0]] = dep[u] + 1;
sum[i[0]] = sum[u] + i[1];
dfs(i[0], u);
}
}
int lca(int a, int b){
if(dep[a] < dep[b]){
swap(a, b);
}
for(int i = 17; i >= 0; i--){
if(dep[a] - (1 << i) >= dep[b]){
a = par[a][i];
}
}
if(a == b){
return a;
}
for(int i = 17; i >= 0; i--){
if(par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
int calcDist(int a, int b){
return sum[a] + sum[b] - 2 * sum[lca(a, b)];
}
int calcSz(int u, int p){
sz[u] = 1;
for(auto i : adj[u]){
if(i[0] == p || done[i[0]]) continue;
sz[u] += calcSz(i[0], u);
}
return sz[u];
}
int get(int u, int p, int x){
for(auto i : adj[u]){
if(i[0] == p || done[i[0]]) continue;
if(sz[i[0]] * 2 > x){
return get(i[0], u, x);
}
}
return u;
}
int build(int u){
int centroid = get(u, u, calcSz(u, u));
done[centroid] = 1;
dists[centroid].push_back({0, centroid, centroid});
for(auto i : adj[centroid]){
if(!done[i[0]]){
int x = build(i[0]);
cenPar[x] = centroid;
for(auto j : dists[x]){
dists[centroid].push_back({calcDist(centroid, j[2]), x, j[2]});
}
}
}
sort(dists[centroid].begin(), dists[centroid].end());
return centroid;
}
int qry(int v, int k){
int cur = v, subtree = v;
int ans = inf;
while(cur){
int goal = k - calcDist(v, cur);
array<int, 3> find = {goal, -inf, -inf};
int lb = lower_bound(dists[cur].begin(), dists[cur].end(), find) - dists[cur].begin();
for(int j = lb; j < dists[cur].size() && dists[cur][j][0] == goal; j++){
if(dists[cur][j][1] == subtree) continue;
int x = dep[v] + dep[cur] - 2 * dep[lca(cur, v)];
int y = dep[dists[cur][lb][2]] + dep[cur] - 2 * dep[lca(dists[cur][lb][2], cur)];
ans = min(ans, x + y);
}
cur = cenPar[cur];
}
return ans;
}
int best_path(int n, int k, int h[][2], int l[]){
for(int i = 0; i < n - 1; i++){
h[i][0]++, h[i][1]++;
adj[h[i][0]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
dfs(1, 1);
build(1);
/*for(int i = 1; i <= n; i++){
cout << i << '\n';
for(auto j : dists[i]){
cout << j[0] << " " << j[1] << " " << j[2] << "\n";
}
cout << '\n';
}*/
int ans = inf;
for(int i = 1; i <= n; i++){
ans = min(ans, qry(i, k));
}
return (ans == inf ? -1 : ans);
}