#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
int ans=N,sz[N],K;
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;
map<int,int> cnt,mn;
void Solve(int u,int p,int dep,int len){
//printf("%i %i %i %i\n",u,p,dep,len);
all.pb({dep,len});
if(K>=dep&&cnt[K-dep]==1)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;
cnt.clear();mn.clear();
cnt[0]=1;
for(auto e:E[u]){
if(!was[e.first]){
Solve(e.first,u,e.second,1);
for(auto c:all){
if(cnt[c.first]==0)cnt[c.first]=1,mn[c.first]=c.second;
else mn[c.first]=min(mn[c.first],c.second);
}
all.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[]){
K=k;
for(int i=0;i<n-1;i++){
int u=h[i][0],v=h[i][1],w=l[i];
//E[u].pb({v,w});
//E[v].pb({u,w});
}
Decompose(0);
if(ans==N)return -1;
else return ans;
}
Compilation message
race.cpp: In function 'int DFS(int, int)':
race.cpp:9:109: warning: no return statement in function returning non-void [-Wreturn-type]
9 | 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];}
| ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:40:13: warning: unused variable 'u' [-Wunused-variable]
40 | int u=h[i][0],v=h[i][1],w=l[i];
| ^
race.cpp:40:23: warning: unused variable 'v' [-Wunused-variable]
40 | int u=h[i][0],v=h[i][1],w=l[i];
| ^
race.cpp:40:33: warning: unused variable 'w' [-Wunused-variable]
40 | int u=h[i][0],v=h[i][1],w=l[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
