Submission #80176

#TimeUsernameProblemLanguageResultExecution timeMemory
80176farukkastamonudaRace (IOI11_race)C++14
9 / 100
3036 ms20264 KiB
#include <bits/stdc++.h> #define fi first #define se second #define lo long long #define inf 1000000000 #define md 1000000007 #define li 200005 #define mp make_pair #define pb push_back using namespace std; int n,k,vis[li],sub[li],mark[li],ans=inf,G[15][2],T[15]; vector< pair<int,int> > v[li],vec; vector<int> sil; int calc(int node,int ata=-1){ sub[node]=0; for(int i=0;i<(int)v[node].size();i++){ int go=v[node][i].fi; if(vis[go]==0 && go!=ata) calc(go,node); } return ++sub[node]; } int find(int node,int ata,int sz){ for(int i=0;i<(int)v[node].size();i++){ int go=v[node][i].fi; if(go!=ata && vis[go]==0 && sub[go]>sz/2){ return find(go,node,sz); } } return node; } void dfs(int node,int ata,int val,int st){ if(val==k) ans=min(ans,st); if(val<k){ ans=min(ans,mark[k-val]+st); vec.pb(mp(val,st)); } for(int i=0;i<(int)v[node].size();i++){ int go=v[node][i].fi; if(go!=ata && vis[go]==0) dfs(go,node,val+v[node][i].se,st+1); } } void solve(int cur=1){ //printf("*"); int cen=find(cur,-1,calc(cur)); sil.clear(); for(int i=0;i<(int)v[cen].size();i++){ int go=v[cen][i].fi; if(vis[go]==1) continue; vec.clear(); dfs(go,cen,v[cen][i].se,1); for(int j=0;j<(int)vec.size();j++){ mark[vec[j].fi]=min(mark[vec[j].fi],vec[j].se); sil.pb(vec[j].fi); } } for(int i=0;i<(int)sil.size();i++){ mark[sil[i]]=inf; } vis[cen]=1; //sil.clear(); for(int i=0;i<(int)v[cen].size();i++){ int git=v[cen][i].fi; if(vis[git]==0) solve(git); } } int best_path(int N,int K,int H[][2],int L[]){ n=N; k=K; for(int i=0;i<n-1;i++){ int u=H[i][0]+1; int vv=H[i][1]+1; int c=L[i]; v[u].pb(mp(vv,c)); v[vv].pb(mp(u,c)); } for(int i=0;i<=k;i++) mark[i]=inf; solve(); if(ans>=inf) ans=-1; return ans; } //~ int main(){ //~ G[0][0]=0,G[0][1]=1; //~ G[1][0]=1,G[1][1]=2; //~ G[2][0]=1,G[2][1]=3; //~ T[0]=1,T[1]=2,T[2]=4; //~ int ty=best_path(4,3,G,T); //~ printf("%d\n",ty); //~ return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...