#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
const int N = 3e4+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;
multiset<int>vis[N];
queue<pair<pii,int>>que;
vector<int>vec[N];
int n,m,dis[N];
int bfs(int st,int end){
for(int i=1;i<=n;i++)
dis[i] = INF;
dis[st] = 0;
que.push({{st,0},0});
while(!que.empty()){
int u = que.front().F.F,dis = que.front().F.S;
int p = que.front().S;
if(u==end)
return dis;
que.pop();
vec[u].push_back(p);
for(auto x:vec[u]){
if(u-x>=1)
if(vis[u-x].find(x)==vis[u-x].end())
que.push({{u-x,dis+1},x}),vis[u-x].insert(x);
if(u+x<=n)
if(vis[u+x].find(x)==vis[u+x].end())
que.push({{u+x,dis+1},x}),vis[u+x].insert(x);
}
}
return -1;
}
int main(){
//freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
int start,end;
for(int i=1;i<=m;i++){
int p,pos;
pos++;
scanf("%d%d",&pos,&p);
vec[pos].push_back(p);
if(i==1)start = pos;
if(i==2)end = pos;
}
printf("%d\n",bfs(start,end));
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%d",&pos,&p);
| ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:72:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | printf("%d\n",bfs(start,end));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:72:11: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
3 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
2 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2416 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
2 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2412 KB |
Output is correct |
8 |
Correct |
2 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
2 ms |
2380 KB |
Output is correct |
11 |
Correct |
3 ms |
2380 KB |
Output is correct |
12 |
Correct |
2 ms |
2380 KB |
Output is correct |
13 |
Correct |
2 ms |
2380 KB |
Output is correct |
14 |
Correct |
16 ms |
2720 KB |
Output is correct |
15 |
Correct |
3 ms |
2508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2412 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
2 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2416 KB |
Output is correct |
8 |
Correct |
2 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
2 ms |
2416 KB |
Output is correct |
11 |
Correct |
2 ms |
2380 KB |
Output is correct |
12 |
Correct |
2 ms |
2380 KB |
Output is correct |
13 |
Correct |
2 ms |
2380 KB |
Output is correct |
14 |
Correct |
15 ms |
2716 KB |
Output is correct |
15 |
Correct |
4 ms |
2672 KB |
Output is correct |
16 |
Correct |
3 ms |
2508 KB |
Output is correct |
17 |
Correct |
3 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2424 KB |
Output is correct |
19 |
Correct |
2 ms |
2380 KB |
Output is correct |
20 |
Correct |
3 ms |
2508 KB |
Output is correct |
21 |
Correct |
2 ms |
2424 KB |
Output is correct |
22 |
Correct |
3 ms |
2380 KB |
Output is correct |
23 |
Correct |
3 ms |
2636 KB |
Output is correct |
24 |
Correct |
4 ms |
2684 KB |
Output is correct |
25 |
Correct |
3 ms |
2424 KB |
Output is correct |
26 |
Correct |
3 ms |
2644 KB |
Output is correct |
27 |
Correct |
3 ms |
2636 KB |
Output is correct |
28 |
Incorrect |
15 ms |
3496 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2416 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
3 ms |
2540 KB |
Output is correct |
7 |
Correct |
2 ms |
2416 KB |
Output is correct |
8 |
Correct |
2 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
3 ms |
2380 KB |
Output is correct |
11 |
Correct |
3 ms |
2380 KB |
Output is correct |
12 |
Correct |
2 ms |
2420 KB |
Output is correct |
13 |
Correct |
3 ms |
2424 KB |
Output is correct |
14 |
Correct |
16 ms |
2692 KB |
Output is correct |
15 |
Correct |
3 ms |
2508 KB |
Output is correct |
16 |
Correct |
2 ms |
2380 KB |
Output is correct |
17 |
Correct |
3 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2380 KB |
Output is correct |
19 |
Correct |
2 ms |
2380 KB |
Output is correct |
20 |
Correct |
3 ms |
2508 KB |
Output is correct |
21 |
Correct |
2 ms |
2380 KB |
Output is correct |
22 |
Correct |
2 ms |
2380 KB |
Output is correct |
23 |
Correct |
3 ms |
2676 KB |
Output is correct |
24 |
Correct |
4 ms |
2764 KB |
Output is correct |
25 |
Correct |
3 ms |
2508 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
3 ms |
2636 KB |
Output is correct |
28 |
Incorrect |
15 ms |
3396 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2420 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
2 ms |
2416 KB |
Output is correct |
7 |
Correct |
2 ms |
2380 KB |
Output is correct |
8 |
Correct |
2 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2416 KB |
Output is correct |
10 |
Correct |
2 ms |
2380 KB |
Output is correct |
11 |
Correct |
3 ms |
2380 KB |
Output is correct |
12 |
Correct |
2 ms |
2380 KB |
Output is correct |
13 |
Correct |
2 ms |
2380 KB |
Output is correct |
14 |
Correct |
16 ms |
2636 KB |
Output is correct |
15 |
Correct |
3 ms |
2552 KB |
Output is correct |
16 |
Correct |
2 ms |
2380 KB |
Output is correct |
17 |
Correct |
4 ms |
2552 KB |
Output is correct |
18 |
Correct |
2 ms |
2380 KB |
Output is correct |
19 |
Correct |
2 ms |
2380 KB |
Output is correct |
20 |
Correct |
3 ms |
2552 KB |
Output is correct |
21 |
Correct |
2 ms |
2424 KB |
Output is correct |
22 |
Correct |
2 ms |
2380 KB |
Output is correct |
23 |
Correct |
4 ms |
2680 KB |
Output is correct |
24 |
Correct |
5 ms |
2764 KB |
Output is correct |
25 |
Correct |
3 ms |
2508 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
3 ms |
2636 KB |
Output is correct |
28 |
Incorrect |
15 ms |
3476 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |