#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int inf=1e9;
int ans=inf,sz[N],K,mn[5*N];
vector<pair<int,int>> E[N];
bool was[N];
int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];}
int Find(int u,int p,int n){for(auto e:E[u])if(e.first!=p&&!was[e.first]&&sz[e.first]*2>n)return Find(e.first,u,n);return u;}
int FindCentroid(int u){DFS(u,u);return Find(u,u,sz[u]);}
vector<pair<int,int>> all,tmp;
void Solve(int u,int p,int dep,int len){
if(dep>K)return;
//printf("%i %i %i %i\n",u,p,dep,len);
all.pb({dep,len});
tmp.pb({dep,len});
if(mn[K-dep]!=inf)ans=min(ans,len+mn[K-dep]);
for(auto e:E[u])if(!was[e.first]&&e.first!=p)Solve(e.first,u,dep+e.second,len+1);
}
void Decompose(int u){
u=FindCentroid(u);
was[u]=1;mn[0]=0;
tmp.pb({0,0});
for(auto e:E[u]){
if(!was[e.first]){
Solve(e.first,u,e.second,1);
for(auto c:all){
if(mn[c.first]==inf)mn[c.first]=c.second;
else mn[c.first]=min(mn[c.first],c.second);
}
all.clear();
}
}
for(auto c:tmp)mn[c.first]=inf;
tmp.clear();
for(auto e:E[u])if(!was[e.first])Decompose(e.first);
}
int best_path(int n,int k,int h[][2],int l[]){
//return -1;
int i;K=k;
for(i=0;i<(n-1);i++){
E[h[i][0]+1].pb(make_pair(h[i][1]+1,l[i]));
E[h[i][1]+1].pb(make_pair(h[i][0]+1,l[i]));
}
for(i=0;i<=k;i++)mn[i]=inf;
Decompose(1);
if(ans==inf)return -1;
else return ans;
}
Compilation message
race.cpp: In function 'int DFS(int, int)':
race.cpp:10:109: warning: no return statement in function returning non-void [-Wreturn-type]
10 | int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];}
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |