#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
int d(int x,int y,vector<vector<pair<int,int> > >&s){
int N=s.size();
vector<int>dis(N,1e9);
dis[x]=0;
priority_queue<pair<int,int> >pq;
pq.push(make_pair(0,x));
while(!pq.empty()){
int nodo=pq.top().second;
int d=-pq.top().first;
pq.pop();
if(d>dis[nodo])
continue;
dis[nodo]=d;
for(pair<int,int>v:s[nodo]){
int vec=v.first;
int dv=v.second;
if(dis[vec]>dis[nodo]+dv){
dis[vec]=dis[nodo]+dv;
pq.push(make_pair(-dis[vec],vec));
}
}
}
if(dis[y]==1e9){
return -1;
}
else{
return dis[y];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N,M,B,P,x,y;
cin>>N>>M;
vector<vector<pair<int,int> > >s(N);
for(int i=0;i<M;i++){
cin>>B>>P;
if(i==0){
x=B;
}
else if(i==1){
y=B;
}
int j=B-P;
int o=1,u=1;
while(j>=0){
s[B].push_back(make_pair(j,o));
j=j-P;
o++;
}
j=B+P;
while(j<=N-1){
s[B].push_back(make_pair(j,u));
j=j+P;
u++;
}
}
cout<<d(x,y,s);
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:72:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | cout<<d(x,y,s);
| ^
skyscraper.cpp:72:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
6 ms |
2588 KB |
Output is correct |
13 |
Correct |
5 ms |
2544 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
2532 KB |
Output is correct |
13 |
Correct |
5 ms |
2544 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
620 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
153 ms |
32492 KB |
Output is correct |
21 |
Correct |
42 ms |
364 KB |
Output is correct |
22 |
Correct |
41 ms |
620 KB |
Output is correct |
23 |
Correct |
42 ms |
492 KB |
Output is correct |
24 |
Correct |
3 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
77 ms |
33476 KB |
Output is correct |
27 |
Correct |
73 ms |
33460 KB |
Output is correct |
28 |
Correct |
2 ms |
620 KB |
Output is correct |
29 |
Correct |
3 ms |
1280 KB |
Output is correct |
30 |
Correct |
2 ms |
748 KB |
Output is correct |
31 |
Correct |
2 ms |
876 KB |
Output is correct |
32 |
Correct |
2 ms |
748 KB |
Output is correct |
33 |
Correct |
4 ms |
1900 KB |
Output is correct |
34 |
Correct |
4 ms |
1900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
42 ms |
364 KB |
Output is correct |
9 |
Correct |
41 ms |
364 KB |
Output is correct |
10 |
Correct |
82 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
6 ms |
2532 KB |
Output is correct |
13 |
Correct |
5 ms |
2544 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
86 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
620 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
75 ms |
32620 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
76 ms |
33476 KB |
Output is correct |
27 |
Correct |
73 ms |
33460 KB |
Output is correct |
28 |
Correct |
2 ms |
620 KB |
Output is correct |
29 |
Correct |
3 ms |
1260 KB |
Output is correct |
30 |
Correct |
2 ms |
748 KB |
Output is correct |
31 |
Correct |
2 ms |
904 KB |
Output is correct |
32 |
Correct |
2 ms |
748 KB |
Output is correct |
33 |
Correct |
4 ms |
1900 KB |
Output is correct |
34 |
Correct |
4 ms |
1900 KB |
Output is correct |
35 |
Correct |
10 ms |
2156 KB |
Output is correct |
36 |
Correct |
2 ms |
620 KB |
Output is correct |
37 |
Correct |
11 ms |
3948 KB |
Output is correct |
38 |
Correct |
141 ms |
3308 KB |
Output is correct |
39 |
Correct |
265 ms |
3436 KB |
Output is correct |
40 |
Correct |
12 ms |
3308 KB |
Output is correct |
41 |
Correct |
229 ms |
3308 KB |
Output is correct |
42 |
Runtime error |
396 ms |
262148 KB |
Execution killed with signal 9 |
43 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
5 ms |
2532 KB |
Output is correct |
13 |
Correct |
5 ms |
2564 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
620 KB |
Output is correct |
18 |
Correct |
41 ms |
492 KB |
Output is correct |
19 |
Correct |
67 ms |
492 KB |
Output is correct |
20 |
Correct |
328 ms |
32492 KB |
Output is correct |
21 |
Correct |
38 ms |
364 KB |
Output is correct |
22 |
Correct |
39 ms |
492 KB |
Output is correct |
23 |
Correct |
2 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
75 ms |
33460 KB |
Output is correct |
27 |
Correct |
72 ms |
33476 KB |
Output is correct |
28 |
Correct |
2 ms |
620 KB |
Output is correct |
29 |
Correct |
3 ms |
1260 KB |
Output is correct |
30 |
Correct |
2 ms |
748 KB |
Output is correct |
31 |
Correct |
2 ms |
876 KB |
Output is correct |
32 |
Correct |
2 ms |
748 KB |
Output is correct |
33 |
Correct |
4 ms |
1900 KB |
Output is correct |
34 |
Correct |
4 ms |
1900 KB |
Output is correct |
35 |
Correct |
9 ms |
2156 KB |
Output is correct |
36 |
Correct |
2 ms |
620 KB |
Output is correct |
37 |
Correct |
13 ms |
3948 KB |
Output is correct |
38 |
Correct |
12 ms |
3308 KB |
Output is correct |
39 |
Correct |
13 ms |
3436 KB |
Output is correct |
40 |
Correct |
14 ms |
3308 KB |
Output is correct |
41 |
Correct |
12 ms |
3180 KB |
Output is correct |
42 |
Runtime error |
617 ms |
262148 KB |
Execution killed with signal 9 |
43 |
Halted |
0 ms |
0 KB |
- |