| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1195438 | Sarvar | Jakarta Skyscrapers (APIO15_skyscraper) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> pwr;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if(!(cin >> n >> m)) return 0;
pwr.assign(n, {});
vector<int> b(m), p(m);
for(int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
pwr[b[i]].push_back(p[i]);
}
int start = b[0], goal = b[1];
const int INF = 4e18;
vector<int> dist(n, INF);
queue<int> q;
dist[start] = 0;
q.push(start);
while(!q.empty()) {
int v = q.front(); q.pop();
for(int idx = 0; idx < (int)pwr[v].size(); idx++) {
int step = pwr[v][idx];
for(int nxt = v + step, add = 1; nxt < n; nxt += step, add++) {
if(dist[nxt] <= dist[v] + add) break;
dist[nxt] = dist[v] + add;
q.push(nxt);
}
for(int nxt = v - step, add = 1; nxt >= 0; nxt -= step, add++) {
if(dist[nxt] <= dist[v] + add) break;
dist[nxt] = dist[v] + add;
q.push(nxt);
}
}
}
cout << (dist[goal] == INF ? -1 : dist[goal]) << '\n';
return 0;
}