#include <bits/stdc++.h>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
const int MAX = 30010;
const int SQ = 173 ;
using namespace std ;
int n , m ;
int b[MAX] , p[MAX] ;
vector<int> content[MAX] ;
vector<int> noName[SQ+5][SQ+5] ;
vector<int> dijkstra(int S)
{
vector<int> dist(n) ;
for(int i = 0 ; i < n ; i++ ) dist[i] = MAX*MAX ;
dist[ b[S] ] = 0 ;
priority_queue< pii , vector<pii> , greater<pii> > fila ;
fila.push(make_pair(0, b[S] ) ) ;
while(!fila.empty() )
{
int d = fila.top().first ;
int curr = fila.top().second ;
fila.pop() ;
if( d != dist[curr] ) continue ;
for(auto e : content[curr] )
{
if( p[e] >= SQ )
{
for(int i = b[e] - p[e], w = 1 ; i >= 0 ; i-= p[e] , w++ )
if( d + w < dist[i] )
{
dist[i] = d + w ;
fila.push(make_pair(d+w, i) ) ;
}
for(int i = b[e] + p[e] , w = 1 ; i < n ; i+= p[e] , w++ )
if( d + w < dist[i] )
{
dist[i] = d + w ;
fila.push(make_pair(d+w, i) ) ;
}
}
else
{
int firstDim = b[e] % p[e] ;
int secondDim = p[e] ;
int x = lower_bound(all(noName[firstDim][secondDim]), b[e]) - noName[firstDim][secondDim].begin() ;
int limLow = (x == 0) ? -1 : noName[firstDim][secondDim][x-1] ;
int limUp = (x == sz(noName[firstDim][secondDim])-1 ) ? -1 : noName[firstDim][secondDim][x+1] ;
for(int i = curr - p[e] , w = 1 ; i >= 0 ; i -= p[e] , w++ )
{
if(d + w < dist[i] )
{
dist[i] = d + w ;
fila.push(make_pair(d+w, i) ) ;
}
if( i == limLow ) break ;
}
for(int i = b[e] + p[e] , w = 1 ; i < n ; i += p[e] , w++ )
{
if(d + w < dist[i] )
{
dist[i] = d + w ;
fila.push(make_pair(d+w, i) ) ;
}
if( i == limUp ) break ;
}
}
}
}
return dist ;
}
int main()
{
scanf("%d%d", &n, &m ) ;
for(int i = 0 ; i < m ; i++ )
{
scanf("%d %d", &b[i] , &p[i] ) ;
content[ b[i] ].push_back(i) ;
if( p[i] < SQ ) noName[ b[i] % p[i] ][ p[i] ].push_back( b[i] ) ;
}
for(int i = 0 ; i < SQ ; i++ )
for(int j = 0 ; j < SQ; j++ )
{
sort(all(noName[i][j]) );
noName[i][j].erase( unique(all(noName[i][j])) , noName[i][j].end() ) ;
}
vector<int> dist = dijkstra(0) ;
if(dist[ b[1] ] == MAX*MAX ) dist[ b[1] ] = -1 ;
printf("%d\n", dist[ b[1] ] ) ;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d%d", &n, &m ) ;
| ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%d %d", &b[i] , &p[i] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1772 KB |
Output is correct |
2 |
Correct |
1 ms |
1772 KB |
Output is correct |
3 |
Correct |
1 ms |
1772 KB |
Output is correct |
4 |
Correct |
1 ms |
1772 KB |
Output is correct |
5 |
Correct |
1 ms |
1772 KB |
Output is correct |
6 |
Correct |
2 ms |
1772 KB |
Output is correct |
7 |
Correct |
1 ms |
1772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1772 KB |
Output is correct |
2 |
Correct |
1 ms |
1772 KB |
Output is correct |
3 |
Correct |
1 ms |
1772 KB |
Output is correct |
4 |
Correct |
1 ms |
1772 KB |
Output is correct |
5 |
Correct |
1 ms |
1772 KB |
Output is correct |
6 |
Correct |
1 ms |
1772 KB |
Output is correct |
7 |
Correct |
1 ms |
1772 KB |
Output is correct |
8 |
Correct |
1 ms |
1772 KB |
Output is correct |
9 |
Correct |
1 ms |
1772 KB |
Output is correct |
10 |
Correct |
2 ms |
1920 KB |
Output is correct |
11 |
Correct |
2 ms |
1900 KB |
Output is correct |
12 |
Correct |
2 ms |
1772 KB |
Output is correct |
13 |
Correct |
3 ms |
1772 KB |
Output is correct |
14 |
Correct |
3 ms |
1900 KB |
Output is correct |
15 |
Correct |
2 ms |
1900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1772 KB |
Output is correct |
2 |
Correct |
1 ms |
1772 KB |
Output is correct |
3 |
Correct |
1 ms |
1772 KB |
Output is correct |
4 |
Correct |
1 ms |
1772 KB |
Output is correct |
5 |
Correct |
2 ms |
1772 KB |
Output is correct |
6 |
Correct |
1 ms |
1772 KB |
Output is correct |
7 |
Correct |
1 ms |
1772 KB |
Output is correct |
8 |
Correct |
1 ms |
1772 KB |
Output is correct |
9 |
Correct |
1 ms |
1772 KB |
Output is correct |
10 |
Correct |
2 ms |
1772 KB |
Output is correct |
11 |
Correct |
3 ms |
1900 KB |
Output is correct |
12 |
Correct |
2 ms |
1772 KB |
Output is correct |
13 |
Correct |
3 ms |
1832 KB |
Output is correct |
14 |
Correct |
2 ms |
1900 KB |
Output is correct |
15 |
Correct |
2 ms |
1900 KB |
Output is correct |
16 |
Correct |
2 ms |
1772 KB |
Output is correct |
17 |
Correct |
2 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1772 KB |
Output is correct |
19 |
Correct |
2 ms |
1772 KB |
Output is correct |
20 |
Correct |
2 ms |
1900 KB |
Output is correct |
21 |
Correct |
2 ms |
1772 KB |
Output is correct |
22 |
Correct |
2 ms |
1772 KB |
Output is correct |
23 |
Correct |
2 ms |
1772 KB |
Output is correct |
24 |
Correct |
3 ms |
1900 KB |
Output is correct |
25 |
Correct |
3 ms |
1900 KB |
Output is correct |
26 |
Correct |
6 ms |
1900 KB |
Output is correct |
27 |
Correct |
6 ms |
1900 KB |
Output is correct |
28 |
Correct |
2 ms |
1900 KB |
Output is correct |
29 |
Correct |
3 ms |
2028 KB |
Output is correct |
30 |
Correct |
2 ms |
1900 KB |
Output is correct |
31 |
Correct |
3 ms |
1900 KB |
Output is correct |
32 |
Correct |
2 ms |
1900 KB |
Output is correct |
33 |
Correct |
4 ms |
2156 KB |
Output is correct |
34 |
Correct |
4 ms |
2156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1772 KB |
Output is correct |
2 |
Correct |
1 ms |
1772 KB |
Output is correct |
3 |
Correct |
2 ms |
1772 KB |
Output is correct |
4 |
Correct |
1 ms |
1772 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
1 ms |
1772 KB |
Output is correct |
7 |
Correct |
1 ms |
1772 KB |
Output is correct |
8 |
Correct |
1 ms |
1772 KB |
Output is correct |
9 |
Correct |
1 ms |
1772 KB |
Output is correct |
10 |
Correct |
2 ms |
1772 KB |
Output is correct |
11 |
Correct |
2 ms |
1900 KB |
Output is correct |
12 |
Correct |
2 ms |
1772 KB |
Output is correct |
13 |
Correct |
2 ms |
1772 KB |
Output is correct |
14 |
Correct |
3 ms |
1900 KB |
Output is correct |
15 |
Correct |
2 ms |
1900 KB |
Output is correct |
16 |
Correct |
2 ms |
1772 KB |
Output is correct |
17 |
Correct |
2 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1772 KB |
Output is correct |
19 |
Correct |
2 ms |
1772 KB |
Output is correct |
20 |
Correct |
2 ms |
1900 KB |
Output is correct |
21 |
Correct |
2 ms |
1772 KB |
Output is correct |
22 |
Correct |
2 ms |
1772 KB |
Output is correct |
23 |
Correct |
2 ms |
1772 KB |
Output is correct |
24 |
Correct |
3 ms |
1900 KB |
Output is correct |
25 |
Correct |
3 ms |
1900 KB |
Output is correct |
26 |
Correct |
7 ms |
1900 KB |
Output is correct |
27 |
Correct |
6 ms |
1900 KB |
Output is correct |
28 |
Correct |
2 ms |
1900 KB |
Output is correct |
29 |
Correct |
3 ms |
2028 KB |
Output is correct |
30 |
Correct |
2 ms |
1900 KB |
Output is correct |
31 |
Correct |
3 ms |
1900 KB |
Output is correct |
32 |
Correct |
3 ms |
1900 KB |
Output is correct |
33 |
Correct |
4 ms |
2156 KB |
Output is correct |
34 |
Correct |
4 ms |
2156 KB |
Output is correct |
35 |
Correct |
10 ms |
2540 KB |
Output is correct |
36 |
Correct |
3 ms |
1900 KB |
Output is correct |
37 |
Correct |
9 ms |
2412 KB |
Output is correct |
38 |
Correct |
12 ms |
2668 KB |
Output is correct |
39 |
Correct |
12 ms |
2668 KB |
Output is correct |
40 |
Correct |
15 ms |
2668 KB |
Output is correct |
41 |
Correct |
11 ms |
2668 KB |
Output is correct |
42 |
Correct |
77 ms |
2684 KB |
Output is correct |
43 |
Correct |
75 ms |
2540 KB |
Output is correct |
44 |
Correct |
10 ms |
2540 KB |
Output is correct |
45 |
Correct |
13 ms |
3052 KB |
Output is correct |
46 |
Correct |
13 ms |
3052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1772 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
2 ms |
1772 KB |
Output is correct |
4 |
Correct |
1 ms |
1772 KB |
Output is correct |
5 |
Correct |
1 ms |
1772 KB |
Output is correct |
6 |
Correct |
1 ms |
1772 KB |
Output is correct |
7 |
Correct |
2 ms |
1772 KB |
Output is correct |
8 |
Correct |
2 ms |
1772 KB |
Output is correct |
9 |
Correct |
2 ms |
1772 KB |
Output is correct |
10 |
Correct |
2 ms |
1772 KB |
Output is correct |
11 |
Correct |
3 ms |
1900 KB |
Output is correct |
12 |
Correct |
2 ms |
1772 KB |
Output is correct |
13 |
Correct |
2 ms |
1772 KB |
Output is correct |
14 |
Correct |
2 ms |
1900 KB |
Output is correct |
15 |
Correct |
2 ms |
1900 KB |
Output is correct |
16 |
Correct |
2 ms |
1772 KB |
Output is correct |
17 |
Correct |
2 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1772 KB |
Output is correct |
19 |
Correct |
2 ms |
1772 KB |
Output is correct |
20 |
Correct |
2 ms |
1900 KB |
Output is correct |
21 |
Correct |
2 ms |
1772 KB |
Output is correct |
22 |
Correct |
2 ms |
1772 KB |
Output is correct |
23 |
Correct |
2 ms |
1772 KB |
Output is correct |
24 |
Correct |
3 ms |
1900 KB |
Output is correct |
25 |
Correct |
3 ms |
1900 KB |
Output is correct |
26 |
Correct |
6 ms |
1900 KB |
Output is correct |
27 |
Correct |
7 ms |
1900 KB |
Output is correct |
28 |
Correct |
2 ms |
1900 KB |
Output is correct |
29 |
Correct |
3 ms |
2028 KB |
Output is correct |
30 |
Correct |
2 ms |
1900 KB |
Output is correct |
31 |
Correct |
3 ms |
1900 KB |
Output is correct |
32 |
Correct |
2 ms |
1900 KB |
Output is correct |
33 |
Correct |
4 ms |
2156 KB |
Output is correct |
34 |
Correct |
4 ms |
2156 KB |
Output is correct |
35 |
Correct |
10 ms |
2540 KB |
Output is correct |
36 |
Correct |
3 ms |
1900 KB |
Output is correct |
37 |
Correct |
9 ms |
2412 KB |
Output is correct |
38 |
Correct |
11 ms |
2668 KB |
Output is correct |
39 |
Correct |
14 ms |
2668 KB |
Output is correct |
40 |
Correct |
12 ms |
2668 KB |
Output is correct |
41 |
Correct |
13 ms |
2668 KB |
Output is correct |
42 |
Correct |
79 ms |
2540 KB |
Output is correct |
43 |
Correct |
75 ms |
2540 KB |
Output is correct |
44 |
Correct |
10 ms |
2540 KB |
Output is correct |
45 |
Correct |
14 ms |
3052 KB |
Output is correct |
46 |
Correct |
13 ms |
3052 KB |
Output is correct |
47 |
Correct |
19 ms |
3304 KB |
Output is correct |
48 |
Correct |
9 ms |
2796 KB |
Output is correct |
49 |
Correct |
9 ms |
2668 KB |
Output is correct |
50 |
Correct |
8 ms |
2540 KB |
Output is correct |
51 |
Correct |
30 ms |
3688 KB |
Output is correct |
52 |
Correct |
31 ms |
3688 KB |
Output is correct |
53 |
Correct |
18 ms |
3688 KB |
Output is correct |
54 |
Correct |
3 ms |
2156 KB |
Output is correct |
55 |
Correct |
3 ms |
2156 KB |
Output is correct |
56 |
Correct |
17 ms |
3444 KB |
Output is correct |
57 |
Correct |
25 ms |
2664 KB |
Output is correct |
58 |
Correct |
983 ms |
2796 KB |
Output is correct |
59 |
Execution timed out |
1031 ms |
2924 KB |
Time limit exceeded |
60 |
Halted |
0 ms |
0 KB |
- |