| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 478719 | byungkyu | 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 ll long long
#define ld long double
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
vector<pii> ch[200005];
vector<ll> st;
set<ll> se;
ll sz[200005],cent[200005],dp[1000005],ret=1e6,l;
ll getsz(ll n,ll pa){
sz[n]=1;
for(auto a : ch[n]){
if(a.fi==pa||cent[a.fi])continue;
sz[n]+=getsz(a.fi,n);
}
return sz[n];
}
ll getcent(ll now,ll pa,ll cap){
ll b,m=cap-sz[now];
for(auto a : ch[now]){
if(a.fi==pa||cent[a.fi])continue;
m=max(m,sz[a.fi]);
b=getcent(a.fi,now,cap);
if(b)return b;
}
if(m*2<=cap)return now;
return 0;
}
ll adjmax(ll now,ll pa){
ll k=0;
for(auto a : ch[now]){
if(a.fi==pa)continue;
if(cent[a.fi])k=max(k,cent[a.fi]);
else k=max(k,adjmax(a.fi,now));
}
return k;
}
void dfs(ll now,ll pa,ll th,ll w,ll dis){
if(w>l)return;
st.push_back(w);
if(l>=w&&dp[l-w]!=-1)ret=min(ret,dp[l-w]+dis);
for(auto a : ch[now]){
if(a.fi==pa)continue;
if(cent[a.fi]<=th)continue;
dfs(a.fi,now,th,w+a.se,dis+1);
}
dp[w]=dis;
}
ll best_path(ll N,ll K,ll H[][2],ll L[]){
ll i,j,k,a,b,c,n;
//scanf("%lld%lld",&n,&l);
n=N;l=K;
for(i=0;i<n-1;i++){
//scanf("%lld%lld%lld",&a,&b,&c);
//a++;b++;
a=H[i][0];b=H[i][1];c=L[i];
a++;b++;
ch[a].push_back({b,c});
ch[b].push_back({a,c});
}
for(i=1;i<=n;i++){
se.insert(i);
}
while(!se.empty()){
a=*se.begin();
k=getsz(a,0);
b=getcent(a,0,k);
cent[b]=adjmax(a,0)+1;
//printf("%lld %lld\n",b,cent[b]);
se.erase(se.find(b));
}
for(i=1;i<=l;i++)dp[i]=-1;
for(i=1;i<=n;i++){
for(auto t : ch[i]){
if(cent[t.fi]<=cent[i])continue;
//printf("new %lld %lld\n",i,t.fi);
dfs(t.fi,i,cent[i],t.se,1);
}
while(st.size()){
dp[st.back()]=-1;
st.pop_back();
}
}
if(ret==1e6)return -1;
return ret;
}