#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//Jakarta Skyscraper
const lg N = 300005;
lg dist[N], in_queue[N];
vector<pair<lg, lg>> adj[N];
vector<lg> b(N), p(N);
void dijkstra(lg src)
{
priority_queue<array<lg, 2>> pq;
pq.push({0, src});
in_queue[src] = 1;
memset(dist, 0x3f, sizeof(dist));
dist[src] = 0;
while(pq.size())
{
lg x = pq.top()[1];
in_queue[x] = 0;
pq.pop();
for(auto [it, c] : adj[x])
{
if(dist[it] > dist[x]+c)
{
dist[it] = dist[x]+c;
if(!in_queue[it]) pq.push({-dist[it], it});
in_queue[it] = true;
}
}
}
return;
}
int main()
{
fastio;
lg n, m;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> b[i] >> p[i];
}
map<array<lg, 2>, lg> mp;
for(int i = 0; i < m; i++)
{
if(mp[{b[i], p[i]}]) continue;
mp[{b[i], p[i]}] = true;
lg x = b[i]+p[i], z = 1;
while(x < n)
{
adj[b[i]].push_back({x, z});
z++;
x += p[i];
}
x = b[i]-p[i];
z = 1;
while(x >= 0)
{
adj[b[i]].push_back({x, z});
z++;
x -= p[i];
}
}
dijkstra(b[0]);
if(dist[b[1]] == dist[N-1])
{
cout << "-1\n";
return 0;
}
cout << dist[b[1]] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14396 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14452 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14660 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14392 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14320 KB |
Output is correct |
| 8 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
10 ms |
14624 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
9 ms |
14552 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14616 KB |
Output is correct |
| 15 |
Correct |
9 ms |
14656 KB |
Output is correct |
| 16 |
Correct |
7 ms |
14524 KB |
Output is correct |
| 17 |
Correct |
8 ms |
14932 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14568 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 20 |
Correct |
75 ms |
78700 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 22 |
Correct |
7 ms |
14492 KB |
Output is correct |
| 23 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 24 |
Correct |
8 ms |
14788 KB |
Output is correct |
| 25 |
Correct |
9 ms |
14676 KB |
Output is correct |
| 26 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 27 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 28 |
Correct |
9 ms |
15052 KB |
Output is correct |
| 29 |
Correct |
8 ms |
15828 KB |
Output is correct |
| 30 |
Correct |
8 ms |
14908 KB |
Output is correct |
| 31 |
Correct |
8 ms |
15160 KB |
Output is correct |
| 32 |
Correct |
9 ms |
14900 KB |
Output is correct |
| 33 |
Correct |
10 ms |
17084 KB |
Output is correct |
| 34 |
Correct |
10 ms |
16960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14648 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14656 KB |
Output is correct |
| 14 |
Correct |
9 ms |
14676 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14652 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 17 |
Correct |
8 ms |
15040 KB |
Output is correct |
| 18 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14524 KB |
Output is correct |
| 20 |
Correct |
77 ms |
78676 KB |
Output is correct |
| 21 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 22 |
Correct |
8 ms |
14528 KB |
Output is correct |
| 23 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 24 |
Correct |
10 ms |
14788 KB |
Output is correct |
| 25 |
Correct |
9 ms |
14676 KB |
Output is correct |
| 26 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 27 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 28 |
Correct |
11 ms |
14932 KB |
Output is correct |
| 29 |
Correct |
9 ms |
15828 KB |
Output is correct |
| 30 |
Correct |
8 ms |
14904 KB |
Output is correct |
| 31 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 32 |
Correct |
7 ms |
14904 KB |
Output is correct |
| 33 |
Correct |
10 ms |
17108 KB |
Output is correct |
| 34 |
Correct |
10 ms |
16976 KB |
Output is correct |
| 35 |
Correct |
26 ms |
19024 KB |
Output is correct |
| 36 |
Correct |
10 ms |
15064 KB |
Output is correct |
| 37 |
Correct |
26 ms |
21676 KB |
Output is correct |
| 38 |
Correct |
31 ms |
21032 KB |
Output is correct |
| 39 |
Correct |
31 ms |
21444 KB |
Output is correct |
| 40 |
Correct |
31 ms |
21180 KB |
Output is correct |
| 41 |
Correct |
37 ms |
20896 KB |
Output is correct |
| 42 |
Correct |
12 ms |
14788 KB |
Output is correct |
| 43 |
Correct |
12 ms |
14704 KB |
Output is correct |
| 44 |
Correct |
79 ms |
78924 KB |
Output is correct |
| 45 |
Correct |
42 ms |
25156 KB |
Output is correct |
| 46 |
Correct |
33 ms |
25016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
7 ms |
14376 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14656 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14584 KB |
Output is correct |
| 14 |
Correct |
9 ms |
14676 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14660 KB |
Output is correct |
| 16 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 17 |
Correct |
9 ms |
14932 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14536 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 20 |
Correct |
80 ms |
78736 KB |
Output is correct |
| 21 |
Correct |
9 ms |
14452 KB |
Output is correct |
| 22 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 23 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 24 |
Correct |
9 ms |
14788 KB |
Output is correct |
| 25 |
Correct |
8 ms |
14784 KB |
Output is correct |
| 26 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 27 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 28 |
Correct |
11 ms |
14932 KB |
Output is correct |
| 29 |
Correct |
8 ms |
15808 KB |
Output is correct |
| 30 |
Correct |
8 ms |
14912 KB |
Output is correct |
| 31 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 32 |
Correct |
8 ms |
14904 KB |
Output is correct |
| 33 |
Correct |
10 ms |
17108 KB |
Output is correct |
| 34 |
Correct |
12 ms |
17008 KB |
Output is correct |
| 35 |
Correct |
26 ms |
19028 KB |
Output is correct |
| 36 |
Correct |
10 ms |
15060 KB |
Output is correct |
| 37 |
Correct |
28 ms |
21696 KB |
Output is correct |
| 38 |
Correct |
29 ms |
21068 KB |
Output is correct |
| 39 |
Correct |
31 ms |
21392 KB |
Output is correct |
| 40 |
Correct |
32 ms |
21196 KB |
Output is correct |
| 41 |
Correct |
31 ms |
20920 KB |
Output is correct |
| 42 |
Correct |
12 ms |
14792 KB |
Output is correct |
| 43 |
Correct |
12 ms |
14688 KB |
Output is correct |
| 44 |
Correct |
78 ms |
78796 KB |
Output is correct |
| 45 |
Correct |
33 ms |
25072 KB |
Output is correct |
| 46 |
Correct |
42 ms |
25016 KB |
Output is correct |
| 47 |
Correct |
63 ms |
36840 KB |
Output is correct |
| 48 |
Correct |
26 ms |
20396 KB |
Output is correct |
| 49 |
Correct |
24 ms |
18632 KB |
Output is correct |
| 50 |
Correct |
19 ms |
18216 KB |
Output is correct |
| 51 |
Correct |
62 ms |
24268 KB |
Output is correct |
| 52 |
Correct |
64 ms |
25588 KB |
Output is correct |
| 53 |
Correct |
29 ms |
19012 KB |
Output is correct |
| 54 |
Correct |
9 ms |
15408 KB |
Output is correct |
| 55 |
Correct |
10 ms |
16592 KB |
Output is correct |
| 56 |
Runtime error |
292 ms |
262144 KB |
Execution killed with signal 9 |
| 57 |
Halted |
0 ms |
0 KB |
- |
