#include <bits/stdc++.h>
using namespace std;
#define B 173
struct t{
int c,x,y;
};
int n,m,b[30005],p[30005];
vector<int>g[30005];
int vis[30005],d[30005][200],q[30005][200];
int main(void){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",b+i,p+i);
g[b[i]].push_back(i);
}
for(int i=0;i<n;i++){
vis[i]=-1;
for(int j=0;j<B;j++)d[i][j]=-1;
}
for(int i=0;i<m;i++)for(int j=0;j<=n/B;j++)q[i][j]=-1;
queue<t>bfs;
bfs.push(t{0,b[0],0});
while(!bfs.empty()){
int c=bfs.front().c,x=bfs.front().x,y=bfs.front().y,z=(x-b[y]%p[y])/p[y];
bfs.pop();
if(x<0||n<=x)continue;
if(vis[x]==-1){
vis[x]=c;
for(int i=0;i<g[x].size();i++){
int u=g[x][i];
bfs.push(t{c+1,x-p[u],u});
bfs.push(t{c+1,x+p[u],u});
}
}
if(p[y]<B&&d[x][p[y]]==-1){
d[x][p[y]]=c;
bfs.push(t{c+1,x-p[y],y});
bfs.push(t{c+1,x+p[y],y});
}
if(p[y]>=B&&q[y][z]==-1){
q[y][z]=c;
bfs.push(t{c+1,x-p[y],y});
bfs.push(t{c+1,x+p[y],y});
}
}
printf("%d\n",vis[b[1]]);
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++){
~^~~~~~~~~~~~
skyscraper.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",b+i,p+i);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 15 |
Correct |
6 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
4 ms |
996 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
6 ms |
3200 KB |
Output is correct |
| 18 |
Correct |
5 ms |
3200 KB |
Output is correct |
| 19 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4224 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 22 |
Correct |
7 ms |
3072 KB |
Output is correct |
| 23 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 24 |
Correct |
8 ms |
4096 KB |
Output is correct |
| 25 |
Correct |
8 ms |
4224 KB |
Output is correct |
| 26 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 27 |
Correct |
8 ms |
4324 KB |
Output is correct |
| 28 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 29 |
Correct |
7 ms |
3200 KB |
Output is correct |
| 30 |
Correct |
31 ms |
2816 KB |
Output is correct |
| 31 |
Correct |
7 ms |
3200 KB |
Output is correct |
| 32 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 33 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 34 |
Correct |
10 ms |
4352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1536 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 15 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
8 ms |
3200 KB |
Output is correct |
| 18 |
Correct |
6 ms |
3200 KB |
Output is correct |
| 19 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 20 |
Correct |
6 ms |
4224 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2304 KB |
Output is correct |
| 22 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 24 |
Correct |
6 ms |
4096 KB |
Output is correct |
| 25 |
Correct |
6 ms |
4224 KB |
Output is correct |
| 26 |
Correct |
6 ms |
4224 KB |
Output is correct |
| 27 |
Correct |
6 ms |
4224 KB |
Output is correct |
| 28 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 29 |
Correct |
9 ms |
3300 KB |
Output is correct |
| 30 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 31 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 32 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 33 |
Correct |
12 ms |
4352 KB |
Output is correct |
| 34 |
Correct |
13 ms |
4352 KB |
Output is correct |
| 35 |
Correct |
39 ms |
23416 KB |
Output is correct |
| 36 |
Correct |
10 ms |
5760 KB |
Output is correct |
| 37 |
Correct |
42 ms |
18944 KB |
Output is correct |
| 38 |
Correct |
52 ms |
27640 KB |
Output is correct |
| 39 |
Correct |
63 ms |
27640 KB |
Output is correct |
| 40 |
Correct |
47 ms |
27640 KB |
Output is correct |
| 41 |
Correct |
45 ms |
27768 KB |
Output is correct |
| 42 |
Correct |
38 ms |
27384 KB |
Output is correct |
| 43 |
Correct |
30 ms |
27384 KB |
Output is correct |
| 44 |
Correct |
29 ms |
27392 KB |
Output is correct |
| 45 |
Correct |
202 ms |
28156 KB |
Output is correct |
| 46 |
Correct |
72 ms |
28152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
5 ms |
3200 KB |
Output is correct |
| 18 |
Correct |
5 ms |
3200 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3072 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4224 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 22 |
Correct |
4 ms |
3072 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 24 |
Correct |
6 ms |
4096 KB |
Output is correct |
| 25 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 26 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 27 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 28 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 29 |
Correct |
7 ms |
3264 KB |
Output is correct |
| 30 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 31 |
Correct |
5 ms |
3072 KB |
Output is correct |
| 32 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 33 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 34 |
Correct |
13 ms |
4352 KB |
Output is correct |
| 35 |
Correct |
35 ms |
23420 KB |
Output is correct |
| 36 |
Correct |
8 ms |
5760 KB |
Output is correct |
| 37 |
Correct |
40 ms |
19064 KB |
Output is correct |
| 38 |
Correct |
48 ms |
27640 KB |
Output is correct |
| 39 |
Correct |
46 ms |
27640 KB |
Output is correct |
| 40 |
Correct |
56 ms |
27620 KB |
Output is correct |
| 41 |
Correct |
44 ms |
27512 KB |
Output is correct |
| 42 |
Correct |
28 ms |
27384 KB |
Output is correct |
| 43 |
Correct |
27 ms |
27364 KB |
Output is correct |
| 44 |
Correct |
34 ms |
27356 KB |
Output is correct |
| 45 |
Correct |
69 ms |
28152 KB |
Output is correct |
| 46 |
Correct |
74 ms |
28112 KB |
Output is correct |
| 47 |
Correct |
115 ms |
31740 KB |
Output is correct |
| 48 |
Correct |
46 ms |
37620 KB |
Output is correct |
| 49 |
Correct |
54 ms |
38392 KB |
Output is correct |
| 50 |
Correct |
39 ms |
35236 KB |
Output is correct |
| 51 |
Correct |
106 ms |
49500 KB |
Output is correct |
| 52 |
Correct |
90 ms |
49532 KB |
Output is correct |
| 53 |
Correct |
66 ms |
49300 KB |
Output is correct |
| 54 |
Correct |
23 ms |
24568 KB |
Output is correct |
| 55 |
Correct |
25 ms |
24704 KB |
Output is correct |
| 56 |
Correct |
58 ms |
49516 KB |
Output is correct |
| 57 |
Correct |
57 ms |
26616 KB |
Output is correct |
| 58 |
Correct |
56 ms |
49400 KB |
Output is correct |
| 59 |
Correct |
62 ms |
49400 KB |
Output is correct |
| 60 |
Correct |
63 ms |
49428 KB |
Output is correct |
| 61 |
Correct |
63 ms |
49400 KB |
Output is correct |
| 62 |
Correct |
105 ms |
49528 KB |
Output is correct |
| 63 |
Correct |
209 ms |
49272 KB |
Output is correct |
| 64 |
Correct |
301 ms |
49272 KB |
Output is correct |
| 65 |
Correct |
561 ms |
49528 KB |
Output is correct |
| 66 |
Correct |
701 ms |
50472 KB |
Output is correct |
| 67 |
Correct |
638 ms |
50424 KB |
Output is correct |
