#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector <int> g[n];
int st, en;
for ( int i = 1; i <= m; i++ ){
int x, y; cin >> x >> y;
g[x].pb(y);
if ( i == 1 ) st = x;
if ( i == 2 ) en = x;
}
const int inf = 1e15 + 1, N = 2e3 + 1;
vector <vector<int>> dis(n, vector <int> (N, inf));
deque <pair<int,int>> dq;
for ( auto i: g[st] ){
dq.pb({st, i});
dis[st][i] = 0;
}
while ( !dq.empty() ){
auto [x, p] = dq.front();
dq.pop_front();
int v = dis[x][p];
if ( x - p >= 0 and chmin(dis[x - p][p], v + 1) ){
dq.pb({x - p, p});
}
if ( x + p < n and chmin(dis[x + p][p], v + 1) ){
dq.pb({x + p, p});
}
for ( auto to: g[x] ){
if ( chmin(dis[x][to], v) ){
dq.push_front({x, to});
}
}
}
int ans = *min_element(all(dis[en]));
if ( ans == inf ) ans = -1;
cout << ans;
cout << '\n';
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:34:9: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | int st, en;
| ^~
skyscraper.cpp:64:38: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
64 | int ans = *min_element(all(dis[en]));
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1868 KB |
Output is correct |
12 |
Correct |
1 ms |
1860 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
3 ms |
1900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
468 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1216 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1864 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
3400 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
12 ms |
27732 KB |
Output is correct |
19 |
Correct |
15 ms |
31684 KB |
Output is correct |
20 |
Correct |
14 ms |
31828 KB |
Output is correct |
21 |
Correct |
3 ms |
6484 KB |
Output is correct |
22 |
Correct |
14 ms |
28244 KB |
Output is correct |
23 |
Correct |
12 ms |
25408 KB |
Output is correct |
24 |
Correct |
14 ms |
30152 KB |
Output is correct |
25 |
Correct |
15 ms |
31804 KB |
Output is correct |
26 |
Correct |
15 ms |
31692 KB |
Output is correct |
27 |
Correct |
15 ms |
31756 KB |
Output is correct |
28 |
Correct |
16 ms |
31852 KB |
Output is correct |
29 |
Correct |
16 ms |
31688 KB |
Output is correct |
30 |
Correct |
17 ms |
31700 KB |
Output is correct |
31 |
Correct |
16 ms |
31700 KB |
Output is correct |
32 |
Correct |
16 ms |
31728 KB |
Output is correct |
33 |
Correct |
17 ms |
31828 KB |
Output is correct |
34 |
Correct |
18 ms |
31816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
3396 KB |
Output is correct |
17 |
Correct |
9 ms |
11988 KB |
Output is correct |
18 |
Correct |
13 ms |
27732 KB |
Output is correct |
19 |
Correct |
15 ms |
31700 KB |
Output is correct |
20 |
Correct |
19 ms |
31820 KB |
Output is correct |
21 |
Correct |
4 ms |
6540 KB |
Output is correct |
22 |
Correct |
18 ms |
28308 KB |
Output is correct |
23 |
Correct |
16 ms |
25428 KB |
Output is correct |
24 |
Correct |
15 ms |
30164 KB |
Output is correct |
25 |
Correct |
15 ms |
31804 KB |
Output is correct |
26 |
Correct |
15 ms |
31700 KB |
Output is correct |
27 |
Correct |
15 ms |
31796 KB |
Output is correct |
28 |
Correct |
16 ms |
31828 KB |
Output is correct |
29 |
Correct |
15 ms |
31700 KB |
Output is correct |
30 |
Correct |
14 ms |
31700 KB |
Output is correct |
31 |
Correct |
16 ms |
31764 KB |
Output is correct |
32 |
Correct |
20 ms |
31772 KB |
Output is correct |
33 |
Correct |
17 ms |
31800 KB |
Output is correct |
34 |
Correct |
19 ms |
31700 KB |
Output is correct |
35 |
Correct |
30 ms |
23724 KB |
Output is correct |
36 |
Correct |
12 ms |
17492 KB |
Output is correct |
37 |
Correct |
39 ms |
31572 KB |
Output is correct |
38 |
Correct |
43 ms |
32736 KB |
Output is correct |
39 |
Correct |
47 ms |
32844 KB |
Output is correct |
40 |
Correct |
50 ms |
32828 KB |
Output is correct |
41 |
Correct |
50 ms |
32844 KB |
Output is correct |
42 |
Correct |
23 ms |
32204 KB |
Output is correct |
43 |
Correct |
24 ms |
32080 KB |
Output is correct |
44 |
Correct |
20 ms |
32252 KB |
Output is correct |
45 |
Correct |
44 ms |
32812 KB |
Output is correct |
46 |
Correct |
54 ms |
32752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
408 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
8 ms |
11988 KB |
Output is correct |
18 |
Correct |
14 ms |
27744 KB |
Output is correct |
19 |
Correct |
14 ms |
31700 KB |
Output is correct |
20 |
Correct |
15 ms |
31828 KB |
Output is correct |
21 |
Correct |
4 ms |
6484 KB |
Output is correct |
22 |
Correct |
14 ms |
28228 KB |
Output is correct |
23 |
Correct |
15 ms |
25428 KB |
Output is correct |
24 |
Correct |
15 ms |
30164 KB |
Output is correct |
25 |
Correct |
15 ms |
31820 KB |
Output is correct |
26 |
Correct |
15 ms |
31700 KB |
Output is correct |
27 |
Correct |
15 ms |
31812 KB |
Output is correct |
28 |
Correct |
18 ms |
31808 KB |
Output is correct |
29 |
Correct |
22 ms |
31712 KB |
Output is correct |
30 |
Correct |
14 ms |
31680 KB |
Output is correct |
31 |
Correct |
15 ms |
31700 KB |
Output is correct |
32 |
Correct |
16 ms |
31700 KB |
Output is correct |
33 |
Correct |
21 ms |
31700 KB |
Output is correct |
34 |
Correct |
22 ms |
31780 KB |
Output is correct |
35 |
Correct |
32 ms |
23696 KB |
Output is correct |
36 |
Correct |
11 ms |
17508 KB |
Output is correct |
37 |
Correct |
43 ms |
31592 KB |
Output is correct |
38 |
Correct |
60 ms |
32820 KB |
Output is correct |
39 |
Correct |
58 ms |
32776 KB |
Output is correct |
40 |
Correct |
45 ms |
32864 KB |
Output is correct |
41 |
Correct |
45 ms |
32852 KB |
Output is correct |
42 |
Correct |
19 ms |
32112 KB |
Output is correct |
43 |
Correct |
26 ms |
32212 KB |
Output is correct |
44 |
Correct |
19 ms |
32160 KB |
Output is correct |
45 |
Correct |
43 ms |
32804 KB |
Output is correct |
46 |
Correct |
41 ms |
32744 KB |
Output is correct |
47 |
Runtime error |
341 ms |
262144 KB |
Execution killed with signal 6 |
48 |
Halted |
0 ms |
0 KB |
- |