#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define MAX 10100
#define MAXS 20
#define INF 1010101010
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> adj[MAX];
int B[MAX];
int P[MAX];
vector<pii> locset;
int N, M;
int findpv(int x) {
int ind = upper_bound(locset.begin(), locset.end(), pii(x, -1)) - locset.begin();
ind--;
if (ind < 0) return -1;
else return locset[ind].second;
}
int findnx(int x) {
int ind = upper_bound(locset.begin(), locset.end(), pii(x, INF)) - locset.begin();
if (ind >= M) return -1;
else return locset[ind].second;
}
int np(int x, int p) {
if (x % p) return x / p * p + p;
else return x;
}
int dist[MAX];
int vis[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M;
int i;
for (i = 0; i < M; i++) cin >> B[i] >> P[i], locset.emplace_back(B[i], i);
sort(locset.begin(), locset.end());
for (i = 0; i < M; i++) {
int delta = 0;
while (1) {
int v = findpv(B[i] - delta);
if (v == -1) break;
if ((B[i] - B[v]) % P[i] == 0) {
adj[i].emplace_back(v, (B[i] - B[v]) / P[i]);
}
delta = B[i] - B[v];
delta = np(delta, P[i]);
if (B[i] < delta) break;
}
delta = 0;
while (1) {
int v = findnx(B[i] + delta);
if (v == -1) break;
if ((B[v] - B[i]) % P[i] == 0) {
adj[i].emplace_back(v, (B[v] - B[i]) / P[i]);
}
delta = B[v] - B[i];
delta = np(delta, P[i]);
if (B[i] + delta >= N) break;
}
}
for (i = 1; i < M; i++) dist[i] = INF;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.emplace(0, 0);
while (pq.size()) {
int v = pq.top().second;
pq.pop();
if (vis[v]) continue;
vis[v] = 1;
for (auto &[x, c] : adj[v]) {
if (vis[x]) continue;
if (dist[x] > dist[v] + c) {
dist[x] = dist[v] + c;
pq.emplace(dist[x], x);
}
}
}
if (dist[1] >= INF) dist[1] = -1;
cout << dist[1] << Ln;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for (auto &[x, c] : adj[v]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
