| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133717 |
2019-07-21T08:56:44 Z |
tinjyu |
Race (IOI11_race) |
C++14 |
|
341 ms |
181212 KB |
#include "race.h"
#include <iostream>
using namespace std;
int tag[200005],road[200005],map[400005][3],t[100000][2],n,k;
int a=10000000,ans[200005][205];
int find(int x)
{
tag[x]=1;
int g=road[x];
//cout<<x<<endl;
while(g!=-1)
{
int now=map[g][0];
if(tag[now]!=1)
{
find(now);
//cout<<x<<" "<<now<<endl;
for(int i=map[g][2];i<=k;i++)
{
a=min(ans[now][i-map[g][2]]+ans[x][k-i]+1,a);
//cout<<ans[now][i-map[g][2]]<<" "<<ans[x][k-i]<<" "<<k-i-map[g][2]<<" ";
}
//cout<<endl;
for(int i=0;i<=k-map[g][2];i++)ans[x][i+map[g][2]]=min(ans[now][i]+1,ans[x][i+map[g][2]]);
}
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<n;i++)
{
for(int j=1;j<=k;j++)ans[i][j]=10000000;
}
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;
}
if(k<=100)
{
find(0);
for(int i=0;i<n;i++)a=min(ans[i][k],a);
if(a==10000000)a=-1;
return a;
}
else
{
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==10000000)a=-1;
return a;
}
}
Compilation message
race.cpp: In function 'int find(int)':
race.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:69:10: warning: array subscript is above array bounds [-Warray-bounds]
t[0][2]=0;
~~~~~~^
race.cpp:84:22: warning: array subscript is above array bounds [-Warray-bounds]
t[pp][2]=t[p][2]+1;
~~~~~~^
race.cpp:84:14: warning: array subscript is above array bounds [-Warray-bounds]
t[pp][2]=t[p][2]+1;
~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
504 KB |
Output is correct |
| 21 |
Incorrect |
25 ms |
1272 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Correct |
156 ms |
86264 KB |
Output is correct |
| 20 |
Correct |
158 ms |
86392 KB |
Output is correct |
| 21 |
Correct |
156 ms |
86264 KB |
Output is correct |
| 22 |
Correct |
160 ms |
86304 KB |
Output is correct |
| 23 |
Correct |
141 ms |
86284 KB |
Output is correct |
| 24 |
Correct |
141 ms |
86392 KB |
Output is correct |
| 25 |
Correct |
164 ms |
88728 KB |
Output is correct |
| 26 |
Correct |
136 ms |
90976 KB |
Output is correct |
| 27 |
Correct |
293 ms |
170836 KB |
Output is correct |
| 28 |
Correct |
301 ms |
181212 KB |
Output is correct |
| 29 |
Correct |
303 ms |
180796 KB |
Output is correct |
| 30 |
Correct |
295 ms |
171000 KB |
Output is correct |
| 31 |
Correct |
296 ms |
171128 KB |
Output is correct |
| 32 |
Correct |
341 ms |
170744 KB |
Output is correct |
| 33 |
Correct |
334 ms |
171256 KB |
Output is correct |
| 34 |
Correct |
223 ms |
170672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
504 KB |
Output is correct |
| 21 |
Incorrect |
25 ms |
1272 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
