#include <bits/stdc++.h>
using namespace std;
int n, m;
int pw[100005];
int pos[100005];
vector <int> doges[100005];
int dist[50005][300];
priority_queue<pair<int,pair<int,int> > > pq;
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &pos[i], &pw[i]);
doges[pos[i]].push_back(i);
}
for (int i = 0; i <= 50000; i++) {
for (int j = 0; j < 300; j++) {
dist[i][j] = 1000000000;
}
}
pq.push(make_pair(0, make_pair(pos[0], 0)));
dist[pos[0]][0] = 0;
int limit = (int) sqrt(n);
int res = 1000000000;
while (!pq.empty()) {
pair<int,pair<int,int> > now = pq.top();
pq.pop();
int posnow = now.second.first;
int distnow = -now.first;
if (posnow == pos[1]) {
res = min(res, distnow);
}
int pownow = now.second.second;
if (pownow == 0) {
for (int i = 0; i < (int)doges[posnow].size(); i++) {
if (pw[doges[posnow][i]] <= limit) {
pair <int,pair<int,int> > nxt;
if (dist[posnow][pw[doges[posnow][i]]] > distnow) {
dist[posnow][pw[doges[posnow][i]]] = distnow;
int distnext = distnow;
pq.push(make_pair(-distnext, make_pair(posnow, pw[doges[posnow][i]])));
}
} else {
int powernow = pw[doges[posnow][i]];
for (int j = 1; posnow - j*powernow >= 0; ++j) {
int posnext = posnow - j*powernow;
int distnext = distnow + j;
if (dist[posnext][0] > distnext) {
dist[posnext][0] = distnext;
pq.push(make_pair(-distnext, make_pair(posnext, 0)));
}
}
for (int j = 1; posnow + j*powernow < n; ++j) {
int posnext = posnow + j*powernow;
int distnext = distnow + j;
if (dist[posnext][0] > distnext) {
dist[posnext][0] = distnext;
pq.push(make_pair(-distnext, make_pair(posnext, 0)));
}
}
}
}
} else {
if (dist[posnow][0] > distnow) {
dist[posnow][0] = distnow;
pq.push(make_pair(-dist[posnow][0], make_pair(posnow, 0)));
}
if (posnow + pownow < n && dist[posnow + pownow][pownow] > dist[posnow][pownow] + 1) {
int distnext = dist[posnow][pownow] + 1;
int posnext = posnow + pownow;
dist[posnext][pownow] = dist[posnow][pownow] + 1;
pq.push(make_pair(-distnext, make_pair(posnext, pownow)));
}
if (posnow - pownow >= 0 && dist[posnow - pownow][pownow] > dist[posnow][pownow] + 1) {
int distnext = dist[posnow][pownow] + 1;
int posnext = posnow - pownow;
dist[posnext][pownow] = dist[posnow][pownow] + 1;
pq.push(make_pair(-distnext, make_pair(posnext, pownow)));
}
}
}
if (res == 1000000000) res = -1;
printf("%d\n",res);
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d %d", &pos[i], &pw[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
62044 KB |
Output is correct |
2 |
Correct |
13 ms |
62044 KB |
Output is correct |
3 |
Correct |
12 ms |
62040 KB |
Output is correct |
4 |
Correct |
12 ms |
62040 KB |
Output is correct |
5 |
Correct |
12 ms |
62044 KB |
Output is correct |
6 |
Correct |
12 ms |
62044 KB |
Output is correct |
7 |
Correct |
12 ms |
62040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
62044 KB |
Output is correct |
2 |
Correct |
12 ms |
62092 KB |
Output is correct |
3 |
Correct |
14 ms |
62108 KB |
Output is correct |
4 |
Correct |
12 ms |
62116 KB |
Output is correct |
5 |
Correct |
13 ms |
62296 KB |
Output is correct |
6 |
Correct |
12 ms |
62044 KB |
Output is correct |
7 |
Correct |
12 ms |
62176 KB |
Output is correct |
8 |
Correct |
13 ms |
62044 KB |
Output is correct |
9 |
Correct |
12 ms |
62064 KB |
Output is correct |
10 |
Correct |
12 ms |
62040 KB |
Output is correct |
11 |
Correct |
12 ms |
62040 KB |
Output is correct |
12 |
Correct |
12 ms |
62140 KB |
Output is correct |
13 |
Correct |
12 ms |
62044 KB |
Output is correct |
14 |
Correct |
13 ms |
62352 KB |
Output is correct |
15 |
Correct |
13 ms |
62044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
62160 KB |
Output is correct |
2 |
Correct |
13 ms |
62124 KB |
Output is correct |
3 |
Correct |
12 ms |
62040 KB |
Output is correct |
4 |
Correct |
12 ms |
62044 KB |
Output is correct |
5 |
Correct |
12 ms |
62040 KB |
Output is correct |
6 |
Correct |
12 ms |
62044 KB |
Output is correct |
7 |
Correct |
13 ms |
62132 KB |
Output is correct |
8 |
Correct |
12 ms |
62040 KB |
Output is correct |
9 |
Correct |
12 ms |
62044 KB |
Output is correct |
10 |
Correct |
12 ms |
62044 KB |
Output is correct |
11 |
Correct |
13 ms |
62164 KB |
Output is correct |
12 |
Correct |
13 ms |
62044 KB |
Output is correct |
13 |
Correct |
13 ms |
62128 KB |
Output is correct |
14 |
Correct |
13 ms |
62044 KB |
Output is correct |
15 |
Correct |
16 ms |
62044 KB |
Output is correct |
16 |
Correct |
12 ms |
62044 KB |
Output is correct |
17 |
Correct |
14 ms |
62184 KB |
Output is correct |
18 |
Correct |
12 ms |
62044 KB |
Output is correct |
19 |
Correct |
12 ms |
62044 KB |
Output is correct |
20 |
Correct |
12 ms |
62040 KB |
Output is correct |
21 |
Correct |
14 ms |
62300 KB |
Output is correct |
22 |
Correct |
12 ms |
62044 KB |
Output is correct |
23 |
Correct |
13 ms |
62044 KB |
Output is correct |
24 |
Correct |
14 ms |
62100 KB |
Output is correct |
25 |
Correct |
14 ms |
62044 KB |
Output is correct |
26 |
Correct |
13 ms |
62044 KB |
Output is correct |
27 |
Correct |
13 ms |
62044 KB |
Output is correct |
28 |
Correct |
13 ms |
62156 KB |
Output is correct |
29 |
Correct |
18 ms |
62044 KB |
Output is correct |
30 |
Correct |
14 ms |
62044 KB |
Output is correct |
31 |
Correct |
16 ms |
62088 KB |
Output is correct |
32 |
Correct |
14 ms |
62044 KB |
Output is correct |
33 |
Correct |
20 ms |
62044 KB |
Output is correct |
34 |
Correct |
21 ms |
62044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
62044 KB |
Output is correct |
2 |
Correct |
12 ms |
62044 KB |
Output is correct |
3 |
Correct |
12 ms |
62044 KB |
Output is correct |
4 |
Correct |
12 ms |
62044 KB |
Output is correct |
5 |
Correct |
12 ms |
62120 KB |
Output is correct |
6 |
Correct |
12 ms |
62044 KB |
Output is correct |
7 |
Correct |
12 ms |
62044 KB |
Output is correct |
8 |
Correct |
13 ms |
62040 KB |
Output is correct |
9 |
Correct |
13 ms |
62044 KB |
Output is correct |
10 |
Correct |
12 ms |
62044 KB |
Output is correct |
11 |
Correct |
13 ms |
62044 KB |
Output is correct |
12 |
Correct |
12 ms |
62040 KB |
Output is correct |
13 |
Correct |
13 ms |
62044 KB |
Output is correct |
14 |
Correct |
12 ms |
62044 KB |
Output is correct |
15 |
Correct |
12 ms |
62044 KB |
Output is correct |
16 |
Correct |
12 ms |
62296 KB |
Output is correct |
17 |
Correct |
13 ms |
62136 KB |
Output is correct |
18 |
Correct |
12 ms |
62044 KB |
Output is correct |
19 |
Correct |
12 ms |
62044 KB |
Output is correct |
20 |
Correct |
13 ms |
62040 KB |
Output is correct |
21 |
Correct |
14 ms |
62176 KB |
Output is correct |
22 |
Correct |
12 ms |
62040 KB |
Output is correct |
23 |
Correct |
13 ms |
62044 KB |
Output is correct |
24 |
Correct |
13 ms |
62044 KB |
Output is correct |
25 |
Correct |
13 ms |
62116 KB |
Output is correct |
26 |
Correct |
13 ms |
62044 KB |
Output is correct |
27 |
Correct |
13 ms |
62044 KB |
Output is correct |
28 |
Correct |
13 ms |
62044 KB |
Output is correct |
29 |
Correct |
19 ms |
62044 KB |
Output is correct |
30 |
Correct |
14 ms |
62040 KB |
Output is correct |
31 |
Correct |
16 ms |
62044 KB |
Output is correct |
32 |
Correct |
14 ms |
62044 KB |
Output is correct |
33 |
Correct |
20 ms |
62212 KB |
Output is correct |
34 |
Correct |
22 ms |
62044 KB |
Output is correct |
35 |
Correct |
20 ms |
62296 KB |
Output is correct |
36 |
Correct |
14 ms |
62044 KB |
Output is correct |
37 |
Correct |
26 ms |
62296 KB |
Output is correct |
38 |
Correct |
24 ms |
62296 KB |
Output is correct |
39 |
Correct |
24 ms |
62296 KB |
Output is correct |
40 |
Correct |
24 ms |
62420 KB |
Output is correct |
41 |
Correct |
24 ms |
62296 KB |
Output is correct |
42 |
Correct |
16 ms |
62300 KB |
Output is correct |
43 |
Correct |
16 ms |
62296 KB |
Output is correct |
44 |
Correct |
16 ms |
62300 KB |
Output is correct |
45 |
Correct |
25 ms |
62372 KB |
Output is correct |
46 |
Correct |
25 ms |
62300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
62144 KB |
Output is correct |
2 |
Correct |
12 ms |
62040 KB |
Output is correct |
3 |
Correct |
13 ms |
62164 KB |
Output is correct |
4 |
Correct |
12 ms |
62044 KB |
Output is correct |
5 |
Correct |
16 ms |
62384 KB |
Output is correct |
6 |
Correct |
12 ms |
62044 KB |
Output is correct |
7 |
Correct |
14 ms |
62044 KB |
Output is correct |
8 |
Correct |
12 ms |
62120 KB |
Output is correct |
9 |
Correct |
12 ms |
62044 KB |
Output is correct |
10 |
Correct |
13 ms |
62076 KB |
Output is correct |
11 |
Correct |
13 ms |
62040 KB |
Output is correct |
12 |
Correct |
14 ms |
62044 KB |
Output is correct |
13 |
Correct |
13 ms |
62160 KB |
Output is correct |
14 |
Correct |
13 ms |
62080 KB |
Output is correct |
15 |
Correct |
13 ms |
62044 KB |
Output is correct |
16 |
Correct |
15 ms |
62296 KB |
Output is correct |
17 |
Correct |
14 ms |
62040 KB |
Output is correct |
18 |
Correct |
13 ms |
62168 KB |
Output is correct |
19 |
Correct |
13 ms |
62044 KB |
Output is correct |
20 |
Correct |
13 ms |
62044 KB |
Output is correct |
21 |
Correct |
12 ms |
62112 KB |
Output is correct |
22 |
Correct |
13 ms |
62056 KB |
Output is correct |
23 |
Correct |
13 ms |
62188 KB |
Output is correct |
24 |
Correct |
13 ms |
62044 KB |
Output is correct |
25 |
Correct |
13 ms |
62040 KB |
Output is correct |
26 |
Correct |
13 ms |
62040 KB |
Output is correct |
27 |
Correct |
13 ms |
62040 KB |
Output is correct |
28 |
Correct |
13 ms |
62044 KB |
Output is correct |
29 |
Correct |
18 ms |
62044 KB |
Output is correct |
30 |
Correct |
14 ms |
62040 KB |
Output is correct |
31 |
Correct |
16 ms |
62044 KB |
Output is correct |
32 |
Correct |
16 ms |
62140 KB |
Output is correct |
33 |
Correct |
20 ms |
62044 KB |
Output is correct |
34 |
Correct |
20 ms |
62044 KB |
Output is correct |
35 |
Correct |
27 ms |
62292 KB |
Output is correct |
36 |
Correct |
14 ms |
62040 KB |
Output is correct |
37 |
Correct |
23 ms |
62300 KB |
Output is correct |
38 |
Correct |
25 ms |
62300 KB |
Output is correct |
39 |
Correct |
24 ms |
62296 KB |
Output is correct |
40 |
Correct |
31 ms |
62296 KB |
Output is correct |
41 |
Correct |
25 ms |
62300 KB |
Output is correct |
42 |
Correct |
16 ms |
62308 KB |
Output is correct |
43 |
Correct |
17 ms |
62296 KB |
Output is correct |
44 |
Correct |
16 ms |
62296 KB |
Output is correct |
45 |
Correct |
25 ms |
62300 KB |
Output is correct |
46 |
Correct |
24 ms |
62300 KB |
Output is correct |
47 |
Correct |
66 ms |
62892 KB |
Output is correct |
48 |
Correct |
17 ms |
62556 KB |
Output is correct |
49 |
Correct |
22 ms |
62556 KB |
Output is correct |
50 |
Correct |
17 ms |
62460 KB |
Output is correct |
51 |
Correct |
50 ms |
63120 KB |
Output is correct |
52 |
Correct |
50 ms |
63500 KB |
Output is correct |
53 |
Correct |
23 ms |
62556 KB |
Output is correct |
54 |
Correct |
13 ms |
62040 KB |
Output is correct |
55 |
Correct |
14 ms |
62040 KB |
Output is correct |
56 |
Correct |
21 ms |
63056 KB |
Output is correct |
57 |
Correct |
65 ms |
62044 KB |
Output is correct |
58 |
Correct |
19 ms |
62300 KB |
Output is correct |
59 |
Correct |
21 ms |
62300 KB |
Output is correct |
60 |
Correct |
23 ms |
62412 KB |
Output is correct |
61 |
Correct |
23 ms |
62356 KB |
Output is correct |
62 |
Correct |
45 ms |
63064 KB |
Output is correct |
63 |
Correct |
43 ms |
63228 KB |
Output is correct |
64 |
Correct |
49 ms |
63072 KB |
Output is correct |
65 |
Correct |
214 ms |
63952 KB |
Output is correct |
66 |
Correct |
623 ms |
63944 KB |
Output is correct |
67 |
Correct |
623 ms |
64208 KB |
Output is correct |