제출 #1272007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272007		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	576 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 = (ll)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];
int id_pos[30009]; // id_pos[position] = index of doge at that position, -1 nếu không có

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> P[i];
    }
    // khởi tạo id_pos
    for (int i = 0; i <= N; ++i) id_pos[i] = -1;
    for (int i = 0; i < M; ++i) {
        id_pos[B[i]] = i;
    }

    // SQ động
    int SQ = max(1, (int)sqrt(N));

    // Precompute small buckets: for p = 1..SQ, groups of indices j by (B[j] % p)
    // small[p][r] => vector of indices j such that B[j] % p == r
    vector<vector<vector<int>>> small(SQ + 1);
    for (int p = 1; p <= SQ; ++p) {
        small[p].assign(p, vector<int>());
    }
    for (int j = 0; j < M; ++j) {
        for (int p = 1; p <= SQ; ++p) {
            int r = B[j] % p;
            small[p][r].push_back(j);
        }
    }

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

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

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        ll du = cur.first;
        int u = cur.second;
        if (du != dista[u]) continue;
        if (u == 1) { // đích là doge index 1
            cout << du << '\n';
            return;
        }

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

        if (step <= SQ) {
            int r = posu % step;
            // Nếu bucket đã rỗng => đã xử lý rồi, skip
            if (!small[step][r].empty()) {
                // duyệt tất cả các node trong bucket
                for (int v : small[step][r]) {
                    ll w = llabs((ll)B[v] - (ll)posu) / step;
                    if (dista[v] > du + w) {
                        dista[v] = du + w;
                        pq.push({dista[v], v});
                    }
                }
                // đảm bảo mỗi bucket xử lý đúng 1 lần
                small[step][r].clear();
            }
        } else {
            // large step: duyệt theo vị trí thực (những vị trí có doge)
            // đi về phải
            for (int x = posu + step; x < N; x += step) {
                int v = id_pos[x];
                if (v != -1) {
                    ll w = (x - posu) / step;
                    if (dista[v] > du + w) {
                        dista[v] = du + w;
                        pq.push({dista[v], v});
                    }
                }
            }
            // đi về trái
            for (int x = posu - step; x >= 0; x -= step) {
                int v = id_pos[x];
                if (v != -1) {
                    ll w = (posu - x) / step;
                    if (dista[v] > du + w) {
                        dista[v] = du + w;
                        pq.push({dista[v], v});
                    }
                }
            }
        }
    }

    cout << -1 << '\n';
}

int main() {
    solve();
    return 0;
}

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