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 "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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |