#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int max_ans = 5000000;
const int maxN = 30005;
const int maxSqrtN = 200;
int n,m;
int zero,one;
int root;
vector<int> powers[maxN];
vector<ll> q[max_ans];
bool done[maxN][maxSqrtN];
ll Encode(int building,int power){
assert(power <= maxSqrtN);
return building + n*power;
}
int dijkstra(){
int curr_ans = 0;
int best_ans = -1;
q[0].pb(Encode(zero,0));
while(curr_ans < max_ans){
if(q[curr_ans].empty()){
curr_ans++;
continue;
}
ll top = q[curr_ans].back();
q[curr_ans].pop_back();
int building = top%n;
int power = top/n;
if(done[building][power]) continue;
done[building][power] = true;
if(building == one){
if(best_ans == -1){
best_ans = curr_ans;
}
continue;
}
//in building
if(!power){
for(ll doge:powers[building]){
//doge in building
if(doge<=root){
q[curr_ans].pb(Encode(building,doge));
} else{
//other building (power>root)
for(int dir=-1;dir<2;dir+=2){
for(int jumps=1;;jumps++){
int pos = building + jumps*dir*doge;
if(pos<0 || pos>=n) break;
q[curr_ans+jumps].pb(Encode(pos,0));
}
}
}
}
} else{
//doge with power <= root
//to building
q[curr_ans].pb(Encode(building,0));
//to other doge
int pos = building + power;
if(pos<n) q[curr_ans+1].pb(Encode(pos,power));
pos = building - power;
if(pos>=0) q[curr_ans+1].pb(Encode(pos,power));
}
}
return best_ans;
}
int main(){
cin>>n>>m;
root = (int)sqrt(n);
for(int i=0;i<m;i++){
int building,power;
cin>>building>>power;
powers[building].pb(power);
if(i==0) zero = building;
if(i==1) one = building;
}
cout<<dijkstra();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
118356 KB |
Output is correct |
2 |
Correct |
59 ms |
118412 KB |
Output is correct |
3 |
Correct |
64 ms |
118296 KB |
Output is correct |
4 |
Correct |
62 ms |
118372 KB |
Output is correct |
5 |
Correct |
63 ms |
118356 KB |
Output is correct |
6 |
Correct |
60 ms |
118412 KB |
Output is correct |
7 |
Correct |
63 ms |
118412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
118364 KB |
Output is correct |
2 |
Correct |
65 ms |
118396 KB |
Output is correct |
3 |
Correct |
60 ms |
118336 KB |
Output is correct |
4 |
Correct |
61 ms |
118380 KB |
Output is correct |
5 |
Correct |
61 ms |
118308 KB |
Output is correct |
6 |
Correct |
60 ms |
118404 KB |
Output is correct |
7 |
Correct |
67 ms |
118420 KB |
Output is correct |
8 |
Correct |
61 ms |
118408 KB |
Output is correct |
9 |
Correct |
63 ms |
118432 KB |
Output is correct |
10 |
Correct |
70 ms |
118452 KB |
Output is correct |
11 |
Correct |
66 ms |
118508 KB |
Output is correct |
12 |
Correct |
62 ms |
118464 KB |
Output is correct |
13 |
Correct |
67 ms |
118488 KB |
Output is correct |
14 |
Correct |
64 ms |
118452 KB |
Output is correct |
15 |
Correct |
62 ms |
118476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
118412 KB |
Output is correct |
2 |
Correct |
63 ms |
118360 KB |
Output is correct |
3 |
Correct |
68 ms |
118316 KB |
Output is correct |
4 |
Correct |
62 ms |
118352 KB |
Output is correct |
5 |
Correct |
61 ms |
118392 KB |
Output is correct |
6 |
Correct |
63 ms |
118328 KB |
Output is correct |
7 |
Correct |
60 ms |
118404 KB |
Output is correct |
8 |
Correct |
62 ms |
118344 KB |
Output is correct |
9 |
Correct |
70 ms |
118416 KB |
Output is correct |
10 |
Correct |
64 ms |
118424 KB |
Output is correct |
11 |
Correct |
64 ms |
118396 KB |
Output is correct |
12 |
Correct |
62 ms |
118408 KB |
Output is correct |
13 |
Correct |
63 ms |
118408 KB |
Output is correct |
14 |
Correct |
62 ms |
118500 KB |
Output is correct |
15 |
Correct |
64 ms |
118476 KB |
Output is correct |
16 |
Correct |
62 ms |
118412 KB |
Output is correct |
17 |
Correct |
63 ms |
118776 KB |
Output is correct |
18 |
Correct |
62 ms |
118544 KB |
Output is correct |
19 |
Correct |
62 ms |
118476 KB |
Output is correct |
20 |
Correct |
63 ms |
118936 KB |
Output is correct |
21 |
Correct |
62 ms |
118436 KB |
Output is correct |
22 |
Correct |
62 ms |
118392 KB |
Output is correct |
23 |
Correct |
62 ms |
118860 KB |
Output is correct |
24 |
Correct |
64 ms |
118960 KB |
Output is correct |
25 |
Correct |
62 ms |
118980 KB |
Output is correct |
26 |
Correct |
64 ms |
118924 KB |
Output is correct |
27 |
Correct |
69 ms |
118860 KB |
Output is correct |
28 |
Correct |
64 ms |
119468 KB |
Output is correct |
29 |
Correct |
65 ms |
120012 KB |
Output is correct |
30 |
Correct |
62 ms |
119200 KB |
Output is correct |
31 |
Correct |
64 ms |
119456 KB |
Output is correct |
32 |
Correct |
73 ms |
119264 KB |
Output is correct |
33 |
Correct |
66 ms |
120880 KB |
Output is correct |
34 |
Correct |
69 ms |
120912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
118344 KB |
Output is correct |
2 |
Correct |
63 ms |
118324 KB |
Output is correct |
3 |
Correct |
62 ms |
118408 KB |
Output is correct |
4 |
Correct |
64 ms |
118400 KB |
Output is correct |
5 |
Correct |
65 ms |
118420 KB |
Output is correct |
6 |
Correct |
63 ms |
118384 KB |
Output is correct |
7 |
Correct |
63 ms |
118292 KB |
Output is correct |
8 |
Correct |
62 ms |
118344 KB |
Output is correct |
9 |
Correct |
62 ms |
118416 KB |
Output is correct |
10 |
Correct |
62 ms |
118424 KB |
Output is correct |
11 |
Correct |
65 ms |
118416 KB |
Output is correct |
12 |
Correct |
66 ms |
118392 KB |
Output is correct |
13 |
Correct |
61 ms |
118488 KB |
Output is correct |
14 |
Correct |
63 ms |
118424 KB |
Output is correct |
15 |
Correct |
63 ms |
118500 KB |
Output is correct |
16 |
Correct |
63 ms |
118352 KB |
Output is correct |
17 |
Correct |
63 ms |
118728 KB |
Output is correct |
18 |
Correct |
62 ms |
118456 KB |
Output is correct |
19 |
Correct |
63 ms |
118420 KB |
Output is correct |
20 |
Correct |
62 ms |
118912 KB |
Output is correct |
21 |
Correct |
61 ms |
118364 KB |
Output is correct |
22 |
Correct |
63 ms |
118440 KB |
Output is correct |
23 |
Correct |
64 ms |
118792 KB |
Output is correct |
24 |
Correct |
67 ms |
118904 KB |
Output is correct |
25 |
Correct |
63 ms |
118920 KB |
Output is correct |
26 |
Correct |
69 ms |
118844 KB |
Output is correct |
27 |
Correct |
64 ms |
118948 KB |
Output is correct |
28 |
Correct |
65 ms |
119372 KB |
Output is correct |
29 |
Correct |
64 ms |
120056 KB |
Output is correct |
30 |
Correct |
64 ms |
119192 KB |
Output is correct |
31 |
Correct |
64 ms |
119464 KB |
Output is correct |
32 |
Correct |
64 ms |
119164 KB |
Output is correct |
33 |
Correct |
66 ms |
120820 KB |
Output is correct |
34 |
Correct |
70 ms |
120816 KB |
Output is correct |
35 |
Correct |
73 ms |
120140 KB |
Output is correct |
36 |
Correct |
65 ms |
118916 KB |
Output is correct |
37 |
Correct |
81 ms |
121112 KB |
Output is correct |
38 |
Correct |
77 ms |
121028 KB |
Output is correct |
39 |
Correct |
78 ms |
121064 KB |
Output is correct |
40 |
Correct |
77 ms |
121052 KB |
Output is correct |
41 |
Correct |
76 ms |
121028 KB |
Output is correct |
42 |
Correct |
84 ms |
119244 KB |
Output is correct |
43 |
Correct |
74 ms |
119244 KB |
Output is correct |
44 |
Correct |
75 ms |
119536 KB |
Output is correct |
45 |
Correct |
78 ms |
123984 KB |
Output is correct |
46 |
Correct |
77 ms |
123960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
118408 KB |
Output is correct |
2 |
Correct |
62 ms |
118420 KB |
Output is correct |
3 |
Correct |
67 ms |
118536 KB |
Output is correct |
4 |
Correct |
74 ms |
118408 KB |
Output is correct |
5 |
Correct |
64 ms |
118372 KB |
Output is correct |
6 |
Correct |
62 ms |
118336 KB |
Output is correct |
7 |
Correct |
60 ms |
118288 KB |
Output is correct |
8 |
Correct |
63 ms |
118320 KB |
Output is correct |
9 |
Correct |
64 ms |
118312 KB |
Output is correct |
10 |
Correct |
67 ms |
118480 KB |
Output is correct |
11 |
Correct |
62 ms |
118412 KB |
Output is correct |
12 |
Correct |
63 ms |
118372 KB |
Output is correct |
13 |
Correct |
64 ms |
118436 KB |
Output is correct |
14 |
Correct |
64 ms |
118416 KB |
Output is correct |
15 |
Correct |
65 ms |
118384 KB |
Output is correct |
16 |
Correct |
64 ms |
118552 KB |
Output is correct |
17 |
Correct |
64 ms |
118732 KB |
Output is correct |
18 |
Correct |
62 ms |
118356 KB |
Output is correct |
19 |
Correct |
62 ms |
118476 KB |
Output is correct |
20 |
Correct |
64 ms |
118856 KB |
Output is correct |
21 |
Correct |
64 ms |
118348 KB |
Output is correct |
22 |
Correct |
71 ms |
118440 KB |
Output is correct |
23 |
Correct |
71 ms |
118960 KB |
Output is correct |
24 |
Correct |
66 ms |
118992 KB |
Output is correct |
25 |
Correct |
64 ms |
118808 KB |
Output is correct |
26 |
Correct |
65 ms |
118884 KB |
Output is correct |
27 |
Correct |
63 ms |
118860 KB |
Output is correct |
28 |
Correct |
67 ms |
119372 KB |
Output is correct |
29 |
Correct |
68 ms |
120112 KB |
Output is correct |
30 |
Correct |
66 ms |
119124 KB |
Output is correct |
31 |
Correct |
70 ms |
119580 KB |
Output is correct |
32 |
Correct |
64 ms |
119148 KB |
Output is correct |
33 |
Correct |
66 ms |
120848 KB |
Output is correct |
34 |
Correct |
66 ms |
120900 KB |
Output is correct |
35 |
Correct |
73 ms |
120100 KB |
Output is correct |
36 |
Correct |
66 ms |
118892 KB |
Output is correct |
37 |
Correct |
73 ms |
121084 KB |
Output is correct |
38 |
Correct |
77 ms |
121024 KB |
Output is correct |
39 |
Correct |
77 ms |
121064 KB |
Output is correct |
40 |
Correct |
80 ms |
121112 KB |
Output is correct |
41 |
Correct |
78 ms |
121100 KB |
Output is correct |
42 |
Correct |
72 ms |
119144 KB |
Output is correct |
43 |
Correct |
71 ms |
119236 KB |
Output is correct |
44 |
Correct |
78 ms |
119564 KB |
Output is correct |
45 |
Correct |
79 ms |
123932 KB |
Output is correct |
46 |
Correct |
79 ms |
123880 KB |
Output is correct |
47 |
Correct |
95 ms |
131520 KB |
Output is correct |
48 |
Correct |
74 ms |
119140 KB |
Output is correct |
49 |
Correct |
77 ms |
119116 KB |
Output is correct |
50 |
Correct |
69 ms |
118848 KB |
Output is correct |
51 |
Correct |
88 ms |
129756 KB |
Output is correct |
52 |
Correct |
88 ms |
130476 KB |
Output is correct |
53 |
Correct |
88 ms |
126156 KB |
Output is correct |
54 |
Correct |
65 ms |
124648 KB |
Output is correct |
55 |
Correct |
68 ms |
125004 KB |
Output is correct |
56 |
Correct |
80 ms |
126380 KB |
Output is correct |
57 |
Correct |
90 ms |
133140 KB |
Output is correct |
58 |
Correct |
78 ms |
126656 KB |
Output is correct |
59 |
Correct |
87 ms |
126372 KB |
Output is correct |
60 |
Correct |
82 ms |
126352 KB |
Output is correct |
61 |
Correct |
82 ms |
126496 KB |
Output is correct |
62 |
Correct |
128 ms |
139000 KB |
Output is correct |
63 |
Correct |
103 ms |
144852 KB |
Output is correct |
64 |
Correct |
115 ms |
149008 KB |
Output is correct |
65 |
Correct |
146 ms |
168940 KB |
Output is correct |
66 |
Correct |
259 ms |
231992 KB |
Output is correct |
67 |
Correct |
255 ms |
231208 KB |
Output is correct |