| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162184 | minhpk | Jakarta Skyscrapers (APIO15_skyscraper) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
int a, b;
vector<int> z[1000005];
int blocksize;
pair<int, int> mark[30005];
struct node {
int val, pos, type;
bool operator>(const node &other) const {
return val > other.val;
}
};
int base;
inline long long encode(int pos, int type) {
return (long long) pos * base + type;
}
unordered_map<long long, int> dist;
void dijkstra() {
priority_queue<node, vector<node>, greater<node>> q;
long long key0 = encode(mark[0].first, mark[0].second);
dist[key0] = 0;
q.push({0, mark[0].first, mark[0].second});
while (!q.empty()) {
node cur = q.top();
q.pop();
int d = cur.val, pos = cur.pos, type = cur.type;
long long curKey = encode(pos, type);
if (dist[curKey] <= d) continue;
if (type == 0) {
for (int p : z[pos]) {
int newPos = pos + p;
if (newPos < a) {
long long key = encode(newPos, p);
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, p});
}
}
newPos = pos - p;
if (newPos >= 0) {
long long key = encode(newPos, p);
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, p});
}
}
}
} else {
long long key0 = encode(pos, 0);
if (!dist.count(key0) || dist[key0] > d) {
dist[key0] = d;
q.push({d, pos, 0});
}
if (type > blocksize) {
int step = 1;
while (pos + step * type < a) {
int newPos = pos + step * type;
long long key = encode(newPos, 0);
int nd = d + step;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, 0});
}
step++;
}
step = 1;
while (pos - step * type >= 0) {
int newPos = pos - step * type;
long long key = encode(newPos, 0);
int nd = d + step;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, 0});
}
step++;
}
} else {
int newPos = pos + type;
if (newPos < a) {
long long key = encode(newPos, type);
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, type});
}
}
newPos = pos - type;
if (newPos >= 0) {
long long key = encode(newPos, type);
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
q.push({nd, newPos, type});
}
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
blocksize = min(a,2*sqrt(a));
base = a + 1;
for (int i = 0; i < b; i++){
int x, y;
cin >> x >> y;
z[x].push_back(y);
mark[i] = {x, y};
}
if(b == 0){
cout << -1;
return 0;
}
dist.reserve(100000);
dijkstra();
long long finalKey = encode(mark[1].first, 0);
if(dist.count(finalKey)){
cout << dist[finalKey];
} else {
cout << -1;
}
return 0;
}