#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 2;
int n, m, b[MAXN], p[MAXN], dis[MAXN], v, tmp, u, x;
vector< int > adj[MAXN];
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++){
scanf("%d%d", &b[i], &p[i]);
adj[b[i]].push_back(p[i]);
}
for(int i = 0;i < n; i ++) dis[i] = INT_MAX;
dis[b[0]] = 0;
priority_queue< pair< int, int> > q;
q.push({0, b[0]});
while( q.size() ){
v = q.top().second, tmp = -q.top().first;
q.pop();
if( dis[v] < tmp || dis[v] == INT_MAX) continue;
for(int i = 0; i < adj[v].size(); i ++){
u = adj[v][i];
x = 1;
for(int i = v + u; i < n; i += u){
if( dis[i] <= dis[v] + x){
x ++;
continue;
}
dis[i] = dis[v] + x, q.push({-dis[i], i}), x ++;
}
x = 1;
for(int i = v - u; i >= 0; i -= u){
if( dis[i] <= dis[v] + x){
x ++;
continue;
}
dis[i] = dis[v] + x, q.push({-dis[i], i}), x ++;
}
}
}
if( dis[b[1]] == INT_MAX) return printf("%d", -1), 0;
printf("%d",dis[b[1]]);
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0; i < adj[v].size(); i ++){
| ~~^~~~~~~~~~~~~~~
skyscraper.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
9 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
11 | scanf("%d%d", &b[i], &p[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7404 KB |
Output is correct |
2 |
Correct |
5 ms |
7404 KB |
Output is correct |
3 |
Correct |
5 ms |
7404 KB |
Output is correct |
4 |
Correct |
5 ms |
7404 KB |
Output is correct |
5 |
Correct |
5 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7404 KB |
Output is correct |
7 |
Correct |
5 ms |
7404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7404 KB |
Output is correct |
2 |
Correct |
5 ms |
7404 KB |
Output is correct |
3 |
Correct |
5 ms |
7404 KB |
Output is correct |
4 |
Correct |
5 ms |
7404 KB |
Output is correct |
5 |
Correct |
5 ms |
7404 KB |
Output is correct |
6 |
Correct |
6 ms |
7404 KB |
Output is correct |
7 |
Correct |
5 ms |
7404 KB |
Output is correct |
8 |
Correct |
5 ms |
7404 KB |
Output is correct |
9 |
Correct |
6 ms |
7404 KB |
Output is correct |
10 |
Correct |
6 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7404 KB |
Output is correct |
2 |
Correct |
5 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
5 ms |
7404 KB |
Output is correct |
5 |
Correct |
5 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7404 KB |
Output is correct |
7 |
Correct |
5 ms |
7404 KB |
Output is correct |
8 |
Correct |
5 ms |
7404 KB |
Output is correct |
9 |
Correct |
5 ms |
7404 KB |
Output is correct |
10 |
Correct |
5 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
5 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
6 ms |
7404 KB |
Output is correct |
19 |
Correct |
5 ms |
7404 KB |
Output is correct |
20 |
Correct |
20 ms |
7532 KB |
Output is correct |
21 |
Correct |
5 ms |
7404 KB |
Output is correct |
22 |
Correct |
5 ms |
7404 KB |
Output is correct |
23 |
Correct |
6 ms |
7404 KB |
Output is correct |
24 |
Correct |
6 ms |
7404 KB |
Output is correct |
25 |
Correct |
6 ms |
7532 KB |
Output is correct |
26 |
Correct |
17 ms |
7404 KB |
Output is correct |
27 |
Correct |
16 ms |
7404 KB |
Output is correct |
28 |
Correct |
7 ms |
7404 KB |
Output is correct |
29 |
Correct |
6 ms |
7532 KB |
Output is correct |
30 |
Correct |
6 ms |
7532 KB |
Output is correct |
31 |
Correct |
6 ms |
7532 KB |
Output is correct |
32 |
Correct |
6 ms |
7532 KB |
Output is correct |
33 |
Correct |
7 ms |
7532 KB |
Output is correct |
34 |
Correct |
8 ms |
7660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7404 KB |
Output is correct |
2 |
Correct |
5 ms |
7404 KB |
Output is correct |
3 |
Correct |
5 ms |
7424 KB |
Output is correct |
4 |
Correct |
5 ms |
7404 KB |
Output is correct |
5 |
Correct |
6 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7404 KB |
Output is correct |
7 |
Correct |
5 ms |
7404 KB |
Output is correct |
8 |
Correct |
5 ms |
7404 KB |
Output is correct |
9 |
Correct |
5 ms |
7404 KB |
Output is correct |
10 |
Correct |
5 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
8 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
6 ms |
7404 KB |
Output is correct |
19 |
Correct |
6 ms |
7404 KB |
Output is correct |
20 |
Correct |
19 ms |
7532 KB |
Output is correct |
21 |
Correct |
5 ms |
7404 KB |
Output is correct |
22 |
Correct |
5 ms |
7404 KB |
Output is correct |
23 |
Correct |
6 ms |
7404 KB |
Output is correct |
24 |
Correct |
6 ms |
7532 KB |
Output is correct |
25 |
Correct |
6 ms |
7532 KB |
Output is correct |
26 |
Correct |
19 ms |
7532 KB |
Output is correct |
27 |
Correct |
17 ms |
7532 KB |
Output is correct |
28 |
Correct |
6 ms |
7404 KB |
Output is correct |
29 |
Correct |
7 ms |
7532 KB |
Output is correct |
30 |
Correct |
6 ms |
7532 KB |
Output is correct |
31 |
Correct |
6 ms |
7660 KB |
Output is correct |
32 |
Correct |
6 ms |
7552 KB |
Output is correct |
33 |
Correct |
7 ms |
7532 KB |
Output is correct |
34 |
Correct |
7 ms |
7660 KB |
Output is correct |
35 |
Correct |
13 ms |
7788 KB |
Output is correct |
36 |
Correct |
7 ms |
7532 KB |
Output is correct |
37 |
Correct |
13 ms |
7916 KB |
Output is correct |
38 |
Correct |
15 ms |
7916 KB |
Output is correct |
39 |
Correct |
15 ms |
7916 KB |
Output is correct |
40 |
Correct |
15 ms |
7916 KB |
Output is correct |
41 |
Correct |
15 ms |
7916 KB |
Output is correct |
42 |
Correct |
193 ms |
7916 KB |
Output is correct |
43 |
Correct |
193 ms |
7916 KB |
Output is correct |
44 |
Correct |
195 ms |
7804 KB |
Output is correct |
45 |
Correct |
13 ms |
7916 KB |
Output is correct |
46 |
Correct |
14 ms |
7916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7404 KB |
Output is correct |
2 |
Correct |
5 ms |
7404 KB |
Output is correct |
3 |
Correct |
5 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
5 ms |
7404 KB |
Output is correct |
6 |
Correct |
5 ms |
7404 KB |
Output is correct |
7 |
Correct |
5 ms |
7404 KB |
Output is correct |
8 |
Correct |
5 ms |
7404 KB |
Output is correct |
9 |
Correct |
6 ms |
7404 KB |
Output is correct |
10 |
Correct |
5 ms |
7404 KB |
Output is correct |
11 |
Correct |
6 ms |
7404 KB |
Output is correct |
12 |
Correct |
6 ms |
7404 KB |
Output is correct |
13 |
Correct |
6 ms |
7404 KB |
Output is correct |
14 |
Correct |
6 ms |
7404 KB |
Output is correct |
15 |
Correct |
6 ms |
7404 KB |
Output is correct |
16 |
Correct |
7 ms |
7404 KB |
Output is correct |
17 |
Correct |
6 ms |
7404 KB |
Output is correct |
18 |
Correct |
6 ms |
7404 KB |
Output is correct |
19 |
Correct |
5 ms |
7404 KB |
Output is correct |
20 |
Correct |
19 ms |
7532 KB |
Output is correct |
21 |
Correct |
5 ms |
7404 KB |
Output is correct |
22 |
Correct |
5 ms |
7404 KB |
Output is correct |
23 |
Correct |
6 ms |
7404 KB |
Output is correct |
24 |
Correct |
6 ms |
7404 KB |
Output is correct |
25 |
Correct |
6 ms |
7532 KB |
Output is correct |
26 |
Correct |
17 ms |
7404 KB |
Output is correct |
27 |
Correct |
18 ms |
7404 KB |
Output is correct |
28 |
Correct |
6 ms |
7404 KB |
Output is correct |
29 |
Correct |
7 ms |
7532 KB |
Output is correct |
30 |
Correct |
6 ms |
7532 KB |
Output is correct |
31 |
Correct |
6 ms |
7532 KB |
Output is correct |
32 |
Correct |
6 ms |
7532 KB |
Output is correct |
33 |
Correct |
7 ms |
7532 KB |
Output is correct |
34 |
Correct |
7 ms |
7660 KB |
Output is correct |
35 |
Correct |
14 ms |
7788 KB |
Output is correct |
36 |
Correct |
7 ms |
7532 KB |
Output is correct |
37 |
Correct |
12 ms |
7788 KB |
Output is correct |
38 |
Correct |
15 ms |
7916 KB |
Output is correct |
39 |
Correct |
15 ms |
7916 KB |
Output is correct |
40 |
Correct |
15 ms |
7916 KB |
Output is correct |
41 |
Correct |
15 ms |
7916 KB |
Output is correct |
42 |
Correct |
193 ms |
7916 KB |
Output is correct |
43 |
Correct |
194 ms |
7936 KB |
Output is correct |
44 |
Correct |
194 ms |
7812 KB |
Output is correct |
45 |
Correct |
13 ms |
7916 KB |
Output is correct |
46 |
Correct |
14 ms |
7916 KB |
Output is correct |
47 |
Correct |
26 ms |
8556 KB |
Output is correct |
48 |
Correct |
13 ms |
8044 KB |
Output is correct |
49 |
Correct |
13 ms |
8172 KB |
Output is correct |
50 |
Correct |
11 ms |
7916 KB |
Output is correct |
51 |
Correct |
35 ms |
9448 KB |
Output is correct |
52 |
Correct |
33 ms |
8940 KB |
Output is correct |
53 |
Correct |
22 ms |
8940 KB |
Output is correct |
54 |
Correct |
7 ms |
7788 KB |
Output is correct |
55 |
Correct |
8 ms |
7788 KB |
Output is correct |
56 |
Execution timed out |
1095 ms |
9088 KB |
Time limit exceeded |
57 |
Halted |
0 ms |
0 KB |
- |