Submission #864092

#TimeUsernameProblemLanguageResultExecution timeMemory
86409220163070Race (IOI11_race)C++14
0 / 100
2 ms19036 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; const int N=4e5+10,INF=1e9; int n,k; int h[N],e[N],ne[N],w[N],idx; int sz[N],mx[N],vis[N],sum,root; pair<int,int> s[N]; int f[N]; int ans; int tp; int q[N]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void getroot(int u,int fa) { sz[u]=1; mx[u]=0; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa||vis[j]) continue; getroot(j,u); sz[u]+=sz[j]; mx[u]=max(mx[u],sz[j]); } mx[u]=max(mx[u],sum-sz[u]); if(mx[root]>mx[u]) root=u; } void getdis(int u,int fa,int d,int p) { if(d>k) return; s[++tp]=make_pair(d,p); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa||vis[j]) continue; getdis(j,u,d+w[i],p+1); } } void solve(int u) { int cnt=0; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(vis[j]) continue; tp=0; getdis(j,u,w[i],1); for(int i=1;i<=tp;i++) ans=min(ans,s[i].second+f[k-s[i].first]); for(int i=1;i<=tp;i++) f[q[++cnt]=s[i].first]=min(f[s[i].first],s[i].second); } for(int i=1;i<=cnt;i++) f[i]=INF; } void dfs(int u) { vis[u]=1; f[0]=0; solve(u); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(vis[j]) continue; root=0; sum=sz[j]; getroot(j,u); dfs(root); } } int best_path(int N, int K, int tt[][2], int l[]) { n=N,k=K; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++) { ++tt[i][0],++tt[i][1]; add(tt[i][0],tt[i][1],l[i]); add(tt[i][1],tt[i][0],l[i]); } for(int i=0;i<=k;i++) f[i]=INF; ans=mx[0]=INF; root=0; sum=n; getroot(1,0); dfs(root); if(ans==INF) return -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...