Submission #1272003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272003		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	10 ms	1860 KiB

skyscraper

#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_

using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll oo = 1e18;

/*----------- I alone decide my fate! ----------*/
   /* Chiec den ong sao, sao 5 canh tuoi mau */

int N, M;
int B[30009], P[30009];
ll dista[30009];
vector<int> pos; // lưu index của các tòa nhà
int id[30009];   // map từ vị trí -> index
const int SQ = 180; // sqrt(30000) ~ 173

struct Node {
    ll d;
    int u;
    bool operator>(const Node& other) const {
        return d > other.d;
    }
};

void solve() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> B[i] >> P[i];
        id[B[i]] = i;
        pos.push_back(B[i]);
    }

    // Dijkstra
    for (int i = 0; i < M; i++) dista[i] = oo;
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    dista[0] = 0;
    pq.push({0, 0});

    // visited modulo classes for small P
    vector<vector<int>> vis(SQ+5, vector<int>(N+5, 0));

    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != dista[u]) continue;
        if (u == 1) {
            cout << du;
            return;
        }

        int step = P[u];
        int posu = B[u];

        if (step <= SQ) {
            int r = posu % step;
            if (vis[step][r]) continue;
            vis[step][r] = 1;
            // duyệt toàn bộ tòa nhà cùng lớp mod
            for (int v = 0; v < M; v++) {
                if (P[v] && B[v] % step == r) {
                    ll w = abs(B[v] - posu) / step;
                    if (dista[v] > du + w) {
                        dista[v] = du + w;
                        pq.push({dista[v], v});
                    }
                }
            }
        } else {
            // large step: duyệt trực tiếp theo jump
            for (int x = posu + step; x <= N; x += step) {
                if (id[x] || id[x]==0) { // tồn tại tòa nhà
                    int v = id[x];
                    if (P[v]) {
                        ll w = (x - posu) / step;
                        if (dista[v] > du + w) {
                            dista[v] = du + w;
                            pq.push({dista[v], v});
                        }
                    }
                }
            }
            for (int x = posu - step; x >= 0; x -= step) {
                if (id[x] || id[x]==0) {
                    int v = id[x];
                    if (P[v]) {
                        ll w = (posu - x) / step;
                        if (dista[v] > du + w) {
                            dista[v] = du + w;
                            pq.push({dista[v], v});
                        }
                    }
                }
            }
        }
    }

    cout << -1;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43