#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
int n,m,B[30005],P[30005],v[30005];
queue<pair<pair<int,int>,int>> q;
vector<int> vt[30005];
bitset<30005> bit[30005];
void f(int now,int p,int cost){
if(!v[now]){
v[now]=1;
for(int i:vt[now]){
if(!bit[now][i]){
bit[now][i]=1;
q.push({{now,i},cost});
}
}
}
if(!bit[now][p]){
bit[now][p]=1;
q.push({{now,p},cost});
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&B[i],&P[i]);
vt[B[i]].push_back(P[i]);
}
v[B[1]]=1;
for(int i:vt[B[1]]){
if(!bit[B[1]][1]){
bit[B[1]][1]=1;
q.push({{B[1],i},0});
}
}
while(!q.empty()){
int now=q.front().x.x,p=q.front().x.y,cost=q.front().y; q.pop();
if(now==B[2]) return !printf("%d",cost);
if(now-p>=0) f(now-p,p,cost+1);
if(now+p<n) f(now+p,p,cost+1);
}
printf("-1");
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
29 | scanf("%d%d",&B[i],&P[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1024 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1024 KB |
Output is correct |
2 |
Correct |
2 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1132 KB |
Output is correct |
10 |
Correct |
2 ms |
1260 KB |
Output is correct |
11 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1008 KB |
Output is correct |
9 |
Correct |
2 ms |
1132 KB |
Output is correct |
10 |
Correct |
2 ms |
1260 KB |
Output is correct |
11 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
2 ms |
1024 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1132 KB |
Output is correct |
10 |
Correct |
2 ms |
1260 KB |
Output is correct |
11 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1132 KB |
Output is correct |
10 |
Correct |
2 ms |
1260 KB |
Output is correct |
11 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |