Submission #464818

#TimeUsernameProblemLanguageResultExecution timeMemory
464818jk410Race (IOI11_race)C++17
43 / 100
3054 ms30132 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; struct edge{ int v,cost; }; const int INF=1e9; int N,K,Ans; int Size[200000],Min_Depth[1000001]; bool Visited[200000]; vector<edge> Edge[200000]; int get_size(int v,int par=-1){ int &ret=Size[v]=1; for (edge i:Edge[v]){ if (Visited[i.v]||i.v==par) continue; ret+=get_size(i.v,v); } return ret; } int get_cent(int v,int sz,int par=-1){ for (edge i:Edge[v]){ if (Visited[i.v]||i.v==par) continue; if (Size[i.v]*2>sz) return get_cent(i.v,sz,v); } return v; } int dfs1(int v,int dist,int par,int depth=1){ if (dist>K) return INF; int ret=min(INF,depth+Min_Depth[K-dist]); for (edge i:Edge[v]){ if (Visited[i.v]||i.v==par) continue; ret=min(ret,dfs1(i.v,dist+i.cost,v,depth+1)); } return ret; } void dfs2(int v,int dist,int par,int depth=1){ if (dist>K) return; Min_Depth[dist]=min(Min_Depth[dist],depth); for (edge i:Edge[v]){ if (Visited[i.v]||i.v==par) continue; dfs2(i.v,dist+i.cost,v,depth+1); } } int solve(int v){ int ret=INF; int cent=get_cent(v,get_size(v)); fill(Min_Depth+1,Min_Depth+K+1,INF); for (edge i:Edge[cent]){ if (Visited[i.v]) continue; ret=min(ret,dfs1(i.v,i.cost,cent)); dfs2(i.v,i.cost,cent); } Visited[cent]=true; for (edge i:Edge[cent]){ if (Visited[i.v]) continue; ret=min(ret,solve(i.v)); } return ret; } int best_path(int n,int k,int h[][2],int l[]){ N=n; K=k; for (int i=0; i<N-1; i++){ Edge[h[i][0]].push_back({h[i][1],l[i]}); Edge[h[i][1]].push_back({h[i][0],l[i]}); } Ans=solve(0); if (Ans==INF) Ans=-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...