#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e15;
void Solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int> > doge(m + 1);
vector<int> positions[n + 1];
for(int i = 1; i <= m; i++) {
cin >> doge[i].first >> doge[i].second; //position, jump;
doge[i].first++;
positions[doge[i].first].push_back(i);
}
vector<bool> vis(m + 1);
vector<int> dist(m + 1);
for(int i = 1; i <= m; i++) {
vis[i] = false;
dist[i] = INF;
}
dist[1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push({dist[1], 1});
while(!pq.empty()) {
int cur_dist = pq.top().first, cur_doge = pq.top().second;
pq.pop();
if(vis[cur_doge]) {
continue;
}
if(cur_doge == 2) {
break;
}
vis[cur_doge] = true;
int cur_skyscraper = doge[cur_doge].first, cur_jump = doge[cur_doge].second;
int new_dist = 1;
for(int i = cur_skyscraper + cur_jump; i <= n; i += cur_jump) {
for(int j = 0; j < positions[i].size(); j++) {
if(vis[positions[i][j]]) {
continue;
}
dist[positions[i][j]] = min(dist[positions[i][j]], cur_dist + new_dist);
pq.push({cur_dist + new_dist, positions[i][j]});
}
new_dist++;
}
new_dist = 1;
for(int i = cur_skyscraper - cur_jump; i > 0; i -= cur_jump) {
for(int j = 0; j < positions[i].size(); j++) {
if(vis[positions[i][j]]) {
continue;
}
dist[positions[i][j]] = min(dist[positions[i][j]], cur_dist + new_dist);
pq.push({cur_dist + new_dist, positions[i][j]});
}
new_dist++;
}
}
if(dist[2] == INF) {
cout << "-1\n";
return;
}
cout << dist[2] << "\n";
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
skyscraper.cpp: In function 'void Solve()':
skyscraper.cpp:41:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j = 0; j < positions[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:52:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int j = 0; j < positions[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
