| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132988 |
2019-07-20T03:30:26 Z |
zozder |
Race (IOI11_race) |
C++14 |
|
3000 ms |
32816 KB |
#include "race.h"
#include <iostream>
#define maxn 2000001
using namespace std;
int map[2*maxn][3],o=0,ans=-1;
int t[maxn];
void find(int x, int k, int num)
{
int p=x;
while(map[p][0]!=-1)
{
p=map[p][0];
if(t[map[p][1]]==0)
{
t[map[p][1]]=1;
if(k-map[p][2]==0)
{
if(num+1<ans||ans==-1)ans=num+1;
}
else if(k-map[p][2]>0)find(map[p][1],k-map[p][2],num+1);
t[map[p][1]]=0;
}
}
}
int best_path(int n, int K, int h[][2], int l[])
{
for(int i=0;i<maxn;i++)
{
map[i][0]=-1;
t[i]=0;
}
o=n-1;
for(int i=0;i<n-1;i++)
{
o++;
map[o][1]=h[i][1];
map[o][2]=l[i];
map[o][0]=map[h[i][0]][0];
map[h[i][0]][0]=o;
o++;
map[o][1]=h[i][0];
map[o][2]=l[i];
map[o][0]=map[h[i][1]][0];
map[h[i][1]][0]=o;
}
// for(int i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
// for(int i=0;i<=o;i++)cout<<map[i][0]<<"\t";cout<<endl;
// for(int i=0;i<=o;i++)cout<<map[i][1]<<"\t";cout<<endl;
for(int i=0;i<n;i++)
{
t[i]=1;
find(i,K,0);
t[i]=0;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 6 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 9 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 10 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 11 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 12 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 13 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 14 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 15 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 16 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 17 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 18 |
Correct |
28 ms |
31608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 6 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 9 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 10 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 11 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 12 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 13 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 14 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 15 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 16 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 17 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 18 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 19 |
Correct |
28 ms |
31676 KB |
Output is correct |
| 20 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 21 |
Correct |
48 ms |
31752 KB |
Output is correct |
| 22 |
Correct |
29 ms |
31692 KB |
Output is correct |
| 23 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 24 |
Correct |
28 ms |
31724 KB |
Output is correct |
| 25 |
Correct |
46 ms |
31736 KB |
Output is correct |
| 26 |
Correct |
30 ms |
31736 KB |
Output is correct |
| 27 |
Correct |
29 ms |
31736 KB |
Output is correct |
| 28 |
Correct |
33 ms |
31608 KB |
Output is correct |
| 29 |
Correct |
39 ms |
31612 KB |
Output is correct |
| 30 |
Correct |
44 ms |
31672 KB |
Output is correct |
| 31 |
Correct |
46 ms |
31612 KB |
Output is correct |
| 32 |
Correct |
46 ms |
31608 KB |
Output is correct |
| 33 |
Correct |
49 ms |
31608 KB |
Output is correct |
| 34 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 35 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 36 |
Correct |
29 ms |
31736 KB |
Output is correct |
| 37 |
Correct |
37 ms |
31736 KB |
Output is correct |
| 38 |
Correct |
39 ms |
31736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 6 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 9 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 10 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 11 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 12 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 13 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 14 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 15 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 16 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 17 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 18 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 19 |
Execution timed out |
3018 ms |
32816 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 6 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 9 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 10 |
Correct |
28 ms |
31612 KB |
Output is correct |
| 11 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 12 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 13 |
Correct |
27 ms |
31608 KB |
Output is correct |
| 14 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 15 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 16 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 17 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 18 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 19 |
Correct |
28 ms |
31676 KB |
Output is correct |
| 20 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 21 |
Correct |
48 ms |
31752 KB |
Output is correct |
| 22 |
Correct |
29 ms |
31692 KB |
Output is correct |
| 23 |
Correct |
28 ms |
31608 KB |
Output is correct |
| 24 |
Correct |
28 ms |
31724 KB |
Output is correct |
| 25 |
Correct |
46 ms |
31736 KB |
Output is correct |
| 26 |
Correct |
30 ms |
31736 KB |
Output is correct |
| 27 |
Correct |
29 ms |
31736 KB |
Output is correct |
| 28 |
Correct |
33 ms |
31608 KB |
Output is correct |
| 29 |
Correct |
39 ms |
31612 KB |
Output is correct |
| 30 |
Correct |
44 ms |
31672 KB |
Output is correct |
| 31 |
Correct |
46 ms |
31612 KB |
Output is correct |
| 32 |
Correct |
46 ms |
31608 KB |
Output is correct |
| 33 |
Correct |
49 ms |
31608 KB |
Output is correct |
| 34 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 35 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 36 |
Correct |
29 ms |
31736 KB |
Output is correct |
| 37 |
Correct |
37 ms |
31736 KB |
Output is correct |
| 38 |
Correct |
39 ms |
31736 KB |
Output is correct |
| 39 |
Execution timed out |
3018 ms |
32816 KB |
Time limit exceeded |
| 40 |
Halted |
0 ms |
0 KB |
- |
