| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 680887 | 1075508020060209tc | 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>
#include "race.h"
using namespace std;
#define int long long
int n;int k;
vector<pair<int,int>>e[200005];
int dp[1000006];
int sz[200005];
int iscen[200005];
int dfssz(int nw,int pa){
int ret=1;
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
if(v==pa||iscen[v]){continue;}
ret+=dfssz(v,nw);
}
sz[nw]=ret;
return ret;
}
void dfscen(int nw,int pa,int nd,int &pl){
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
if(v==pa||iscen[v]){continue;}
dfscen(v,nw,nd,pl);
}
if(pl==0&&sz[nw]>nd/2){
pl=nw;
}
}
int ans=1e8;
void dfs(int nw,int pa,int dis,int d,int ad){
if(dis<=k&&ad==0){
ans=min(ans,d+dp[k-dis]);
}
if(ad==1){
if(dis<=k){dp[dis]=min(dp[dis],d);}
}
if(ad==-1){
if(dis<=k){dp[dis]=1e7;}
}
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;int w=e[nw][i].second;
if(iscen[v]||v==pa){continue;}
dfs(v,nw,dis+w,d+1,ad);
}
}
void solve(int rt){
int cen=0;
dfscen(rt,0,dfssz(rt,0),cen);
dp[0]=0;
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
dfs(v,cen,w,1,0);
dfs(v,cen,w,1,1);
}
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
dfs(v,cen,w,1,-1);
}
iscen[cen]=1;
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
cin>>n>>k;
for(int i=0;i<=k;i++){
dp[i]=1e7;
}
for(int i=1;i<=n-1;i++){
int a;int b;int c;
cin>>a>>b>>c;
a++;b++;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
solve(1);
if(ans<=200000){
cout<<ans<<endl;
return ans;
}else{
cout<<-1<<endl;
return -1;
}
}
signed main(){
}