#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;
const int MAXN = (int)2e5 + 5;
const int INF = 1e18;
int pos[MAXN], p[MAXN];
vector <pii> g[MAXN];
int n, m;
void create(int pos, int x) {
if (x == 0) { // wtf
return;
}
for (int i = pos % x; i < n; i += x) {
if (i != pos) {
g[pos].pb({abs(pos - i) / x, i});
}
}
}
int dist[MAXN];
signed main() {
fastInp;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> pos[i] >> p[i];
create(pos[i], p[i]);
}
for (int i = 1; i <= 1e5; i++) {
cerr << "ok" << endl;
}
memset(dist, -1, sizeof(dist));
dist[pos[0]] = 0;
queue <pii> pq;
pq.push({0, pos[0]});
while (!pq.empty()) {
int v = pq.front().sc;
int cost = -pq.front().fr;
pq.pop();
if (cost > dist[v]) {
continue;
}
for (auto el : g[v]) {
int c = el.fr, to = el.sc;
if (dist[to] == -1 || dist[to] > dist[v] + c) {
dist[to] = dist[v] + c;
pq.push({-dist[to], to});
}
}
}
cout << dist[pos[1]] << endl;
}
/*
4 4
1 1
0 1
3 4
2 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
6824 KB |
Output is correct |
2 |
Correct |
304 ms |
6832 KB |
Output is correct |
3 |
Correct |
311 ms |
6792 KB |
Output is correct |
4 |
Correct |
328 ms |
6780 KB |
Output is correct |
5 |
Correct |
317 ms |
6832 KB |
Output is correct |
6 |
Correct |
310 ms |
6768 KB |
Output is correct |
7 |
Correct |
347 ms |
6836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
364 ms |
6788 KB |
Output is correct |
2 |
Correct |
306 ms |
6752 KB |
Output is correct |
3 |
Correct |
305 ms |
6944 KB |
Output is correct |
4 |
Correct |
329 ms |
6844 KB |
Output is correct |
5 |
Correct |
303 ms |
6952 KB |
Output is correct |
6 |
Correct |
309 ms |
6792 KB |
Output is correct |
7 |
Correct |
305 ms |
6840 KB |
Output is correct |
8 |
Correct |
305 ms |
6772 KB |
Output is correct |
9 |
Correct |
306 ms |
6852 KB |
Output is correct |
10 |
Correct |
303 ms |
6844 KB |
Output is correct |
11 |
Correct |
301 ms |
7108 KB |
Output is correct |
12 |
Correct |
307 ms |
10096 KB |
Output is correct |
13 |
Correct |
326 ms |
10032 KB |
Output is correct |
14 |
Correct |
312 ms |
7008 KB |
Output is correct |
15 |
Correct |
309 ms |
6984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
6852 KB |
Output is correct |
2 |
Correct |
307 ms |
6852 KB |
Output is correct |
3 |
Correct |
299 ms |
6812 KB |
Output is correct |
4 |
Correct |
312 ms |
6852 KB |
Output is correct |
5 |
Correct |
308 ms |
6904 KB |
Output is correct |
6 |
Correct |
301 ms |
6852 KB |
Output is correct |
7 |
Correct |
305 ms |
6828 KB |
Output is correct |
8 |
Correct |
304 ms |
6840 KB |
Output is correct |
9 |
Correct |
303 ms |
6840 KB |
Output is correct |
10 |
Correct |
303 ms |
6912 KB |
Output is correct |
11 |
Correct |
302 ms |
7072 KB |
Output is correct |
12 |
Correct |
310 ms |
10160 KB |
Output is correct |
13 |
Correct |
308 ms |
9984 KB |
Output is correct |
14 |
Correct |
302 ms |
6980 KB |
Output is correct |
15 |
Correct |
310 ms |
7084 KB |
Output is correct |
16 |
Correct |
305 ms |
6944 KB |
Output is correct |
17 |
Correct |
314 ms |
7412 KB |
Output is correct |
18 |
Correct |
347 ms |
7016 KB |
Output is correct |
19 |
Correct |
312 ms |
7056 KB |
Output is correct |
20 |
Correct |
372 ms |
71104 KB |
Output is correct |
21 |
Correct |
300 ms |
6884 KB |
Output is correct |
22 |
Correct |
308 ms |
7172 KB |
Output is correct |
23 |
Correct |
303 ms |
6960 KB |
Output is correct |
24 |
Correct |
309 ms |
7108 KB |
Output is correct |
25 |
Correct |
311 ms |
6980 KB |
Output is correct |
26 |
Correct |
392 ms |
71048 KB |
Output is correct |
27 |
Correct |
389 ms |
70936 KB |
Output is correct |
28 |
Correct |
303 ms |
7304 KB |
Output is correct |
29 |
Correct |
321 ms |
8340 KB |
Output is correct |
30 |
Correct |
303 ms |
7364 KB |
Output is correct |
31 |
Correct |
307 ms |
7816 KB |
Output is correct |
32 |
Correct |
306 ms |
7308 KB |
Output is correct |
33 |
Correct |
307 ms |
9508 KB |
Output is correct |
34 |
Correct |
310 ms |
9280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
305 ms |
6824 KB |
Output is correct |
2 |
Correct |
321 ms |
6900 KB |
Output is correct |
3 |
Correct |
299 ms |
6824 KB |
Output is correct |
4 |
Correct |
303 ms |
6848 KB |
Output is correct |
5 |
Correct |
301 ms |
6848 KB |
Output is correct |
6 |
Correct |
311 ms |
6848 KB |
Output is correct |
7 |
Correct |
308 ms |
6884 KB |
Output is correct |
8 |
Correct |
304 ms |
6828 KB |
Output is correct |
9 |
Correct |
306 ms |
6840 KB |
Output is correct |
10 |
Correct |
305 ms |
6852 KB |
Output is correct |
11 |
Correct |
308 ms |
7072 KB |
Output is correct |
12 |
Correct |
327 ms |
10092 KB |
Output is correct |
13 |
Correct |
305 ms |
10032 KB |
Output is correct |
14 |
Correct |
306 ms |
7108 KB |
Output is correct |
15 |
Correct |
315 ms |
6916 KB |
Output is correct |
16 |
Correct |
300 ms |
6984 KB |
Output is correct |
17 |
Correct |
305 ms |
7352 KB |
Output is correct |
18 |
Correct |
302 ms |
6988 KB |
Output is correct |
19 |
Correct |
304 ms |
7068 KB |
Output is correct |
20 |
Correct |
384 ms |
70980 KB |
Output is correct |
21 |
Correct |
310 ms |
6896 KB |
Output is correct |
22 |
Correct |
305 ms |
6956 KB |
Output is correct |
23 |
Correct |
303 ms |
7044 KB |
Output is correct |
24 |
Correct |
306 ms |
7152 KB |
Output is correct |
25 |
Correct |
305 ms |
7004 KB |
Output is correct |
26 |
Correct |
400 ms |
71016 KB |
Output is correct |
27 |
Correct |
393 ms |
70884 KB |
Output is correct |
28 |
Correct |
302 ms |
7692 KB |
Output is correct |
29 |
Correct |
305 ms |
8276 KB |
Output is correct |
30 |
Correct |
312 ms |
7352 KB |
Output is correct |
31 |
Correct |
307 ms |
7564 KB |
Output is correct |
32 |
Correct |
307 ms |
7364 KB |
Output is correct |
33 |
Correct |
307 ms |
9524 KB |
Output is correct |
34 |
Correct |
319 ms |
9284 KB |
Output is correct |
35 |
Correct |
313 ms |
10180 KB |
Output is correct |
36 |
Correct |
302 ms |
7208 KB |
Output is correct |
37 |
Correct |
327 ms |
13424 KB |
Output is correct |
38 |
Correct |
315 ms |
12220 KB |
Output is correct |
39 |
Correct |
318 ms |
12608 KB |
Output is correct |
40 |
Correct |
322 ms |
12800 KB |
Output is correct |
41 |
Correct |
320 ms |
12588 KB |
Output is correct |
42 |
Runtime error |
260 ms |
262148 KB |
Execution killed with signal 9 |
43 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
304 ms |
6784 KB |
Output is correct |
2 |
Correct |
314 ms |
6868 KB |
Output is correct |
3 |
Correct |
311 ms |
6800 KB |
Output is correct |
4 |
Correct |
309 ms |
6852 KB |
Output is correct |
5 |
Correct |
315 ms |
6852 KB |
Output is correct |
6 |
Correct |
303 ms |
6844 KB |
Output is correct |
7 |
Correct |
308 ms |
6780 KB |
Output is correct |
8 |
Correct |
304 ms |
6836 KB |
Output is correct |
9 |
Correct |
306 ms |
6800 KB |
Output is correct |
10 |
Correct |
330 ms |
6868 KB |
Output is correct |
11 |
Correct |
309 ms |
7108 KB |
Output is correct |
12 |
Correct |
313 ms |
10200 KB |
Output is correct |
13 |
Correct |
313 ms |
10036 KB |
Output is correct |
14 |
Correct |
313 ms |
7000 KB |
Output is correct |
15 |
Correct |
305 ms |
6980 KB |
Output is correct |
16 |
Correct |
303 ms |
6956 KB |
Output is correct |
17 |
Correct |
340 ms |
7328 KB |
Output is correct |
18 |
Correct |
338 ms |
6948 KB |
Output is correct |
19 |
Correct |
312 ms |
6980 KB |
Output is correct |
20 |
Correct |
382 ms |
71080 KB |
Output is correct |
21 |
Correct |
331 ms |
6852 KB |
Output is correct |
22 |
Correct |
302 ms |
7084 KB |
Output is correct |
23 |
Correct |
315 ms |
6920 KB |
Output is correct |
24 |
Correct |
311 ms |
7136 KB |
Output is correct |
25 |
Correct |
320 ms |
7000 KB |
Output is correct |
26 |
Correct |
411 ms |
71024 KB |
Output is correct |
27 |
Correct |
392 ms |
70836 KB |
Output is correct |
28 |
Correct |
311 ms |
7348 KB |
Output is correct |
29 |
Correct |
309 ms |
8180 KB |
Output is correct |
30 |
Correct |
308 ms |
7296 KB |
Output is correct |
31 |
Correct |
312 ms |
7620 KB |
Output is correct |
32 |
Correct |
315 ms |
7336 KB |
Output is correct |
33 |
Correct |
317 ms |
9432 KB |
Output is correct |
34 |
Correct |
314 ms |
9304 KB |
Output is correct |
35 |
Correct |
335 ms |
10232 KB |
Output is correct |
36 |
Correct |
333 ms |
7224 KB |
Output is correct |
37 |
Correct |
325 ms |
13476 KB |
Output is correct |
38 |
Correct |
315 ms |
12160 KB |
Output is correct |
39 |
Correct |
343 ms |
12704 KB |
Output is correct |
40 |
Correct |
318 ms |
12716 KB |
Output is correct |
41 |
Correct |
345 ms |
12576 KB |
Output is correct |
42 |
Runtime error |
280 ms |
262148 KB |
Execution killed with signal 9 |
43 |
Halted |
0 ms |
0 KB |
- |