| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 441260 | julian33 | 경주 (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>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
const int mxN=2e5+5,mxK=1e6+5;
vector<pll> graph[mxN];
int seen[mxN],sub[mxN],ans=1e9,K,N;
int mp[mxK];
vector<int> path;
int dfs(int at,int p){
sub[at]=1;
for(pll &u:graph[at]){
int i=u.first; int w=u.second;
if(i==p || seen[i])
continue;
sub[at]+=dfs(i,at);
}
return sub[at];
}
int centroid(int at,int p,int s){
for(pll &u:graph[at]){
int i=u.first; int w=u.second;
if(i==p || seen[i])
continue;
if(2*sub[i]>=s)
return centroid(i,at,s);
}
return at;
}
void solve(int at,int p,ll len,int filling,int h){
if(len>K)
return;
if(filling){
path.pb(len);
mina(mp[len],h);
} else{
mina(ans,mp[K-len]+h);
}
for(pll &u:graph[at]){
int i=u.first; int w=u.second;
if(i==p || seen[i])
continue;
solve(i,at,len+w,filling,h+1);
}
}
void build(int at){
int s=dfs(at,-1);
int cent=centroid(at,-1,s);
mp[0]=0;
for(pll &u:graph[cent]){
int i=u.first; int w=u.second;
if(!seen[i]){
solve(i,cent,w,0,1);
solve(i,cent,w,1,1);
}
}
while(sz(path)){
mp[path.back()]=1e9;
path.pop_back();
}
seen[cent]=1;
for(pll &u:graph[cent]){
int i=u.first; int w=u.second;
if(!seen[i])
build(i);
}
}
int best_path(int n,int k,int h[][2],int l[]){
N=n; K=k;
for(int i=0;i<n-1;i++){
graph[h[i][0]].pb({graph[h[i][1]],l[i]});
graph[h[i][1]].pb({graph[h[i][0]],l[i]});
}
fill(mp,mp+K+1,1e9);
build(0);
return ans==1e9?-1:ans;
}