| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162202 | minhpk | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
const int MAX_POS = 300005;
const int MAX_TYPE = 3005;
const long long INF = 1e18;
int a, b;
vector<int> z[MAX_POS];
int blocksize;
pair<int, int> mark[30005];
struct node {
int val, pos, type;
bool operator>(const node &other) const {
return val > other.val;
}
};
static long long dp[MAX_POS][MAX_TYPE];
void dijkstra() {
for (int i = 0; i < a; i++) {
for (int t = 0; t < MAX_TYPE; t++) {
dp[i][t] = INF;
}
}
int startPos = mark[0].first, startType = mark[0].second;
dp[startPos][startType] = 0;
priority_queue<node, vector<node>, greater<node>> pq;
pq.push({0, startPos, startType});
while (!pq.empty()) {
node cur = pq.top();
pq.pop();
int d = cur.val, pos = cur.pos, type = cur.type;
if (dp[pos][type] < d) continue;
if (type == 0) {
for (int p : z[pos]) {
int newPos = pos + p;
if (newPos < a && p < MAX_TYPE) {
if (dp[newPos][p] > d + 1) {
dp[newPos][p] = d + 1;
pq.push({d + 1, newPos, p});
}
}
newPos = pos - p;
if (newPos >= 0 && p < MAX_TYPE) {
if (dp[newPos][p] > d + 1) {
dp[newPos][p] = d + 1;
pq.push({d + 1, newPos, p});
}
}
}
} else {
if (dp[pos][0] > d) {
dp[pos][0] = d;
pq.push({d, pos, 0});
}
if (type > blocksize) {
for (int step = 1; pos + step * type < a; step++) {
int newPos = pos + step * type;
if (dp[newPos][0] > d + step) {
dp[newPos][0] = d + step;
pq.push({d + step, newPos, 0});
}
}
for (int step = 1; pos - step * type >= 0; step++) {
int newPos = pos - step * type;
if (dp[newPos][0] > d + step) {
dp[newPos][0] = d + step;
pq.push({d + step, newPos, 0});
}
}
} else {
int newPos = pos + type;
if (newPos < a && type < MAX_TYPE) {
if (dp[newPos][type] > d + 1) {
dp[newPos][type] = d + 1;
pq.push({d + 1, newPos, type});
}
}
newPos = pos - type;
if (newPos >= 0 && type < MAX_TYPE) {
if (dp[newPos][type] > d + 1) {
dp[newPos][type] = d + 1;
pq.push({d + 1, newPos, type});
}
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
blocksize = sqrt(a);
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;
}
dijkstra();
int finalPos = mark[1].first;
if (dp[finalPos][0] < INF)
cout << dp[finalPos][0];
else
cout << -1;
return 0;
}