| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 592088 | Hackapie | 경주 (Race) (IOI11_race) | C++17 | 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 int
#define mp make_pair
#include "race.h"
using namespace std;
int ans;
const ll lim=200005;
const ll lim2=2000000;
vector<bool> vis(lim);
vector<pair<int,int>> g[lim];
vector<int> par(lim);
int kk;
vector<int> sz(lim);
int timer=1;
vector<int> ok(lim2),add(lim2);
map<int,int>add;
void dfs_sz(int node,int p){
sz[node]=1;
for(auto x:g[node]){
if(x.first==p)continue;
if(vis[x.first])continue;
dfs_sz(x.first,node);
sz[node]+=sz[x.first];
}
}
int centroid(int &cnt,int node,int p){
for(auto x:g[node]){
if(x.first==p)continue;
if(vis[x.first])continue;
if(sz[x.first]>(cnt/2)){
centroid(cnt,x.first,node);
}
}
return node;
}
void solve(int node,int p,ll dis,int cnt,vector<pair<ll,ll>> &info){
if(dis<=kk && ok[kk-dis]==timer){ //if a valid path exists
ans=min(ans,cnt+add[kk-dis]);
}
if(dis<=kk){
info.push_back({dis,cnt}); //record information
for(auto x:g[node]){
if(x.first==p)continue;
if(!vis[x.first]){
solve(x.first,node,dis+x.second,cnt+1,info);
}
}
}
}
void create(int root,int p){
dfs_sz(root,p); //-> find size
int c=centroid(sz[root],root,p); //find new centroid
vis[c]=true; //visited
++timer;
ok[0]=timer;
add[0]=0;
par[c]=root; //updating info
for(auto x:g[c]){ //for every subtree in centroid find paths ..will help in finding if there exists some path that posses through centrod
if(vis[x.first])continue;
if(x.first==p)continue;
vector<pair<ll,ll>> v;
solve(x.first,c,x.second,1,v);
for(auto y:v){ //updating info
if(ok[y.first]!=timer){
ok[y.first]=timer;
add[y.first]=y.second;
}else{
if(add[y.first]>y.second){
ok[y.first]=timer;
add[y.first]=y.second;
}
}
}
}
for(auto x:g[c]){
if(x.first==p)continue; //centroid decom
if(!vis[x.first])create(x.first,c);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
ans=2*n;
vis.clear();
sz.clear();
par.clear();
for(int i=1;i<=n;i++)g[i].clear();
timer=1;
kk=k;
ok.clear();
add.clear();
for(int i=0;i<n-1;i++){
g[h[i][0]].push_back({h[i][1],l[i]});
g[h[i][1]].push_back({h[i][0],l[i]});
}
create(1,-1);
if(ans==(2*n))ans=-1;
return ans;
}