#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));
queue <pair<int,int>> q;
for ( auto i: g[st] ){
q.push({st, i});
dis[0][i] = 0;
}
while ( !q.empty() ){
auto [x, p] = q.front();
q.pop();
int v = dis[x][p], y = x, step = 0;
while ( y >= p ){
y -= p; ++step;
if ( chmin(dis[y][p], v + step) ){
q.push({y, p});
}
for ( auto i: g[y] ){
if ( chmin(dis[y][i], v + step) ){
q.push({y, i});
}
}
}
step = 0;
while ( x + p < n ){
x += p; ++step;
if ( chmin(dis[x][p], v + step) ){
q.push({x, p});
}
for ( auto i: g[x] ){
if ( chmin(dis[x][i], v + step) ){
q.push({x, i});
}
}
}
}
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:76:38: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | int ans = *min_element(all(dis[en]));
| ^
# |
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 |
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 |
448 KB |
Output is correct |
7 |
Correct |
1 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
320 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 |
444 KB |
Output is correct |
8 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
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 |
444 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
320 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 |
8 |
Incorrect |
1 ms |
828 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
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 |
480 KB |
Output is correct |
8 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |