#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;
///--------------------------------
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(f, x) memset(f, x, sizeof(f))
#define uniqueV(x) sort(all(x)), (x).resize(unique(all(x)) - x.begin())
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
///--------------------------------
#define PROBLEM "test"
const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL
///--------------------------------
void precalc();
void solve();
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(PROBLEM".inp", "r")) {
freopen(PROBLEM".inp", "r", stdin);
freopen(PROBLEM".out", "w", stdout);
}
constexpr bool MULTI_TEST = 0;
int t = 1;
if (MULTI_TEST) cin >> t;
while (t--)
solve();
// cerr << setprecision(3) << fixed;
// cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
}
///--------------------[PROBLEM SOLUTION]--------------------///
const int BLOCKSZ = 200;
const int maxn = 30030;
ll dist[maxn][BLOCKSZ + 1];
bool vis[maxn][BLOCKSZ + 1];
vector<ll> spec[maxn];
ll n, m, P[maxn], B[maxn];
void solve() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> B[i] >> P[i];
spec[B[i]].pb(P[i]);
}
mem(dist, 0x3f);
mem(vis, false);
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
auto addHeavy = [&](int x, int y, ll D) -> void {
for (int nx = x % y; nx < n; nx += y) {
if (!vis[nx][BLOCKSZ] && minimize(dist[nx][BLOCKSZ], D + abs(nx - x) / y))
pq.push({dist[nx][BLOCKSZ], nx, BLOCKSZ});
}
};
if (P[0] >= BLOCKSZ)
addHeavy(B[0], P[0], 0);
dist[B[0]][BLOCKSZ] = 0;
pq.push({0, B[0], BLOCKSZ});
while (pq.size()) {
int x = pq.top()[1], y = pq.top()[2]; pq.pop();
if (vis[x][y]) continue;
vis[x][y] = true;
if (y == BLOCKSZ) {
for (ll cy : spec[x]) {
if (cy < BLOCKSZ) {
if (!vis[x][cy] && minimize(dist[x][cy], dist[x][y]))
pq.push({dist[x][cy], x, cy});
}
else addHeavy(x, cy, dist[x][BLOCKSZ]);
}
spec[x].clear();
continue;
}
//dummy vertex
if (x - y >= 0 && !vis[x - y][BLOCKSZ]
&& minimize(dist[x - y][BLOCKSZ], dist[x][y] + 1))
pq.push({dist[x - y][BLOCKSZ], x - y, BLOCKSZ});
if (x + y < n && !vis[x + y][BLOCKSZ]
&& minimize(dist[x + y][BLOCKSZ], dist[x][y] + 1))
pq.push({dist[x + y][BLOCKSZ], x + y, BLOCKSZ});
//direct path
if (x - y >= 0 && !vis[x - y][y]
&& minimize(dist[x - y][y], dist[x][y] + 1))
pq.push({dist[x - y][y], x - y, y});
if (x + y < n && !vis[x + y][y]
&& minimize(dist[x + y][y], dist[x][y] + 1))
pq.push({dist[x + y][y], x + y, y});
}
cout << (!vis[B[1]][BLOCKSZ] ? -1 : dist[B[1]][BLOCKSZ]) << '\n';
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen(PROBLEM".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen(PROBLEM".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
54616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
54620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
54364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
54616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
54616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
