| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1215862 | zhenja | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;
# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937 mt(time(0));
const int N = 1e5 + 2, inf = 1e9 + 100, mod = 1e9 + 7, mod2 = 998244353, P = 257;
const ll llinf = 1e18 + 1000;
int n, m;
ll dist[N];
vector<pair<int, int>> g[N];
map<int, vector<int>> a[N];
void solve() {
cin >> n >> m;
int st, ansx, ansb;
for (int i = 0; i < m; ++i) {
if (i == 1) {
cin >> ansx >> ansb;
} else {
int x, b;
cin >> x >> b;
if (i == 0) st = x;
a[b][x % b].push_back(x);
}
}
for (int b = 1; b < n; ++b) {
for (auto x : a[b]) {
vector<int> pos = x.second;
for (int i = 0; i < pos.size(); ++i) {
int v = pos[i];
for (int to = v - b; to >= (i == 0 ? 0 : pos[i - 1]); to -= b) g[v].push_back({ to, (v - to) / b });
for (int to = v + b; to <= (i + 1 == pos.size() ? n - 1 : pos[i + 1]); to += b) g[v].push_back({ to, (to - v) / b });
}
}
}
fill(dist, dist + n, llinf);
dist[st] = 0;
priority_queue<pair<ll, int>> q;
q.push({ 0, st });
while(!q.empty()){
ll d = -q.top().first;
int v = q.top().second;
q.pop();
if (dist[v] < d) continue;
for (auto p : g[v]) {
int to = p.first, w = p.second;
if (d + w < dist[to]) {
dist[to] = d + w;
q.push({ -dist[to], to });
}
}
}
cout << (dist[ansx] == llinf ? -1 : dist[ansx]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("coloring.in", "r", stdin);
//freopen("coloring.out", "w", stdout);
//ld time1 = clock();
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
cout << '\n';
cout.flush();
}
//ld time2 = clock();
//cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
return 0;
}