| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1293342 | settop | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
const int MAXN=2e5+10;
const int MAXL=20;
typedef pair<int,int> pii;
int ancestral[MAXN][MAXL],dp[MAXN],ans=1e9,k,dep[MAXN];
ll sparse[MAXN][MAXL];
set<pii> g[MAXN];
set<pair<ll,int>> caras[MAXN];
vector<int> child[MAXN],lista[MAXN];
void dfsini(int x,int p){
for(auto [u,j]:g[x])
if(u!=p){
ancestral[u][0]=x;
sparse[u][0]=j;
dep[u]=dep[x]+1;
dfsini(u,x);
}
}
void dfs(int x,int p){
dp[x]=1;
for(auto[u,j]:g[x]) if(u!=p) dfs(u,x),dp[x]+=dp[u];
}
int get_centroid(int x,int p,int sub){
for(auto [u,j]:g[x])
if(u!=p && 2*dp[u]>sub) return get_centroid(u,x,sub);
return x;
}
void build(int x,int p){
dfs(x,p);
int centroid=get_centroid(x,p,dp[x]);
child[p].pb(centroid);
vector<pii> adj(all(g[centroid]));
for(auto [u,j]:adj){
g[u].erase({centroid,j});
g[centroid].erase({u,j});
build(u,centroid);
}
}
pair<ll,ll> dist(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
ll r=0,r1=0;
rfall(i,MAXL-1,0){
if(dep[a]-(1<<i)>=dep[b]){
r+=(1<<i);
r1+=sparse[a][i];
a=ancestral[a][i];
}
}
if(a==b) return{r,r1};
rfall(i,MAXL-1,0){
if(ancestral[a][i]!=ancestral[b][i] && ancestral[a][i] && ancestral[b][i]){
r+=2*(1<<i);
r1+=sparse[a][i]+sparse[b][i];
a=ancestral[a][i];
b=ancestral[b][i];
}
}
r+=2,r1+=sparse[a][0]+sparse[b][0];
return{r,r1};
}
void calc(int x){
caras[x].insert({0,0});
lista[x].pb(x);
for(auto u:child[x]){
calc(u);
for(auto i:lista[u]){
auto d=dist(x,i);
auto it=caras[x].lower_bound({k-d.S,-1});
if(it!=caras[x].end() && (*it).F==k-d.S) ans=min(ans,d.F+(*it).S);
}
for(auto i:lista[u]){
auto d=dist(x,i);
caras[x].insert({d.S,d.F});
lista[x].pb(i);
}
}
}
int best_path(int n, int K, int H[][2], int L[]){
fall(i,0,n-2){
int a=H[i][0],b=H[i][1]; a++,b++;
g[a].insert({b,L[i]});
g[b].insert({a,L[i]});
}
k=K;
dfsini(1,0);
fall(j,1,MAXL-1)
fall(i,1,n) ancestral[i][j]=ancestral[ancestral[i][j-1]][j-1],sparse[i][j]=sparse[i][j-1]+sparse[ancestral[i][j-1]][j-1];
build(1,0);
calc(child[0][0]);
return(ans==1e9?-1:ans);
}