Submission #132972

#TimeUsernameProblemLanguageResultExecution timeMemory
132972tinjyuRace (IOI11_race)C++14
21 / 100
3032 ms5852 KiB
#include "race.h" #include <iostream> using namespace std; int point[200005],tagt[200005],t[200005][3],pt=0,p=0,a=9999999,tag[200005],ans[10000][105],road[200005],map[4000005][3],n,k; int find(int x) { tag[x]=1; int g=road[x]; //cout<<x<<endl; int c=1; while(g!=-1) { int now=map[g][0]; if(tag[now]!=1) { find(now); if(tagt[x]==0) { pt++; point[x]=pt; tagt[x]=1; c=0; } //cout<<x<<" "<<now<<" "<<pt<<" "<<point[now]<<endl; for(int i=k-map[g][2];i>=0;i--) { //cout<<ans[point[now]][i]<<" "; if(ans[point[now]][i]!=-1) { if(ans[pt][i+map[g][2]]!=-1)ans[pt][i+map[g][2]]=min(ans[pt][i]+1,ans[point[now]][i+map[g][2]]); else ans[pt][i+map[g][2]]=ans[point[now]][i]+1; } //cout<<ans[pt][i+map[g][2]]<<" "; } p++; //cout<<endl; } g=map[g][1]; } if(ans[point[x]][k]!=-1)a=min(a,ans[point[x]][k]); //cout<<c<<endl; if(c==0)pt--; //cout<<x<<" "<<point[x]<<endl; //for(int i=0;i<=k;i++)cout<<ans[point[x]][i]<<" "; //cout<<endl; } int f(int x,int tmp,int an) { tag[x]=1; if(tmp>k)return 0; if(tmp==k) { a=min(an,a); return 0; } int g=road[x]; while(g!=-1) { int now=map[g][0]; if(tag[now]!=1) { f(now,tmp+map[g][2],an+1); } g=map[g][1]; } } int best_path(int N, int K, int H[][2], int L[]) { n=N,k=K; /*for(int i=0;i<10000;i++) { for(int j=1;j<=k;j++)ans[i][j]=-1; }*/ for(int i=0;i<n;i++)road[i]=-1; for(int i=0;i<n-1;i++) { int x=H[i][0],y=H[i][1]; map[i*2][0]=y; map[i*2][1]=road[x]; map[i*2][2]=L[i]; road[x]=i*2; map[i*2+1][0]=x; map[i*2+1][1]=road[y]; map[i*2+1][2]=L[i]; road[y]=i*2+1; } //find(0); for(int i=0;i<n;i++) { for(int j=0;j<n;j++)tag[j]=0; int p=0,pp=0; t[0][0]=i; t[0][1]=0; t[0][2]=0; tag[i]=1; while(p<=pp) { int x=t[p][0]; int g=road[x]; while(g!=-1) { int now=map[g][0]; if(tag[now]==0) { tag[now]=1; pp++; t[pp][0]=now; t[pp][1]=t[p][1]+map[g][2]; t[pp][2]=t[p][2]+1; if(t[pp][1]==k) { a=min(a,t[pp][2]); //cout<<now<<t<<endl; } } g=map[g][1]; } p++; } } if(a==9999999)a=-1; return a; }

Compilation message (stderr)

race.cpp: In function 'int find(int)':
race.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int f(int, int, int)':
race.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...