Submission #1272010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272010		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	720 KiB

skyscraper

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

using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> B(M), P(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> P[i];
        // assume B[i] in [0, N-1]
    }

    // pos_at[x] = list of doge indices located at position x
    vector<vector<int>> pos_at(N);
    for (int i = 0; i < M; ++i) pos_at[B[i]].push_back(i);

    int SQ = max(1, (int)sqrt(N));

    // small[p][r] : for p <= SQ, bucket of doge 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
    vector<ll> dist(M, INF);
    dist[0] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, 0});

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

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

        if (step <= SQ) {
            int r = posu % step;
            // nếu bucket r chưa bị xử lý, duyệt tất cả phần tử trong bucket
            if (!small[step][r].empty()) {
                for (int v : small[step][r]) {
                    ll w = llabs((ll)B[v] - (ll)posu) / step;
                    if (dist[v] > du + w) {
                        dist[v] = du + w;
                        pq.push({dist[v], v});
                    }
                }
                // đảm bảo mỗi bucket chỉ xử lý 1 lần
                vector<int>().swap(small[step][r]); // clear + free
            }
        } else {
            // large step: duyệt các vị trí posu +/- k*step trong [0, N-1]
            for (int x = posu + step; x < N; x += step) {
                for (int v : pos_at[x]) {
                    ll w = (ll)(x - posu) / step;
                    if (dist[v] > du + w) {
                        dist[v] = du + w;
                        pq.push({dist[v], v});
                    }
                }
            }
            for (int x = posu - step; x >= 0; x -= step) {
                for (int v : pos_at[x]) {
                    ll w = (ll)(posu - x) / step;
                    if (dist[v] > du + w) {
                        dist[v] = du + w;
                        pq.push({dist[v], v});
                    }
                }
            }
        }
    }

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

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