Submission #1272017

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

skyscraper

#include <bits/stdc++.h>
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];

    int Bsq = max(1, (int)floor(sqrt((double)N)));

    // positions -> list of doges at that building
    vector<vector<int>> pos_at(N);
    for (int i = 0; i < M; ++i) pos_at[B[i]].push_back(i);

    // dist for small states (pos, p) where p in [1..Bsq]
    // encode idx = pos*(Bsq+1) + p (we ignore p=0)
    int Pcount = Bsq + 1;
    long long small_nodes = 1LL * N * Pcount;
    vector<ll> dist_small;
    dist_small.assign((size_t)small_nodes, INF);

    // dist for doges (for any p > Bsq we store per-doge)
    vector<ll> dist_doge(M, INF);

    auto idx_small = [&](int pos, int p)->int{
        return pos * Pcount + p;
    };

    // priority queue: tuple (dist, type, id, p_if_small)
    // type: 0 = small state, id = pos, p given; 1 = doge state, id = doge index
    using State = tuple<ll,int,int,int>;
    // (dist, type, id, p)
    priority_queue<State, vector<State>, greater<State>> pq;

    // initial: doge 0 has news
    if (P[0] <= Bsq) {
        int id = idx_small(B[0], P[0]);
        dist_small[id] = 0;
        pq.emplace(0LL, 0, B[0], P[0]);
    } else {
        dist_doge[0] = 0;
        pq.emplace(0LL, 1, 0, 0);
    }

    while (!pq.empty()) {
        auto [d, type, id, p] = pq.top(); pq.pop();
        if (type == 0) {
            int pos = id;
            int pp = p;
            int id0 = idx_small(pos, pp);
            if (d != dist_small[id0]) continue;

            // If there are doges at this pos, we can pass news with cost 0
            for (int doge : pos_at[pos]) {
                if (P[doge] <= Bsq) {
                    int id2 = idx_small(pos, P[doge]);
                    if (dist_small[id2] > d) {
                        dist_small[id2] = d;
                        pq.emplace(d, 0, pos, P[doge]);
                    }
                } else {
                    if (dist_doge[doge] > d) {
                        dist_doge[doge] = d;
                        pq.emplace(d, 1, doge, 0);
                    }
                }
            }

            // Jump to pos +/- pp (cost 1 each)
            int pos2 = pos + pp;
            if (pos2 < N) {
                int id2 = idx_small(pos2, pp);
                if (dist_small[id2] > d + 1) {
                    dist_small[id2] = d + 1;
                    pq.emplace(d + 1, 0, pos2, pp);
                }
            }
            pos2 = pos - pp;
            if (pos2 >= 0) {
                int id2 = idx_small(pos2, pp);
                if (dist_small[id2] > d + 1) {
                    dist_small[id2] = d + 1;
                    pq.emplace(d + 1, 0, pos2, pp);
                }
            }
        } else {
            int u = id;
            if (d != dist_doge[u]) continue;
            if (u == 1) { // reached doge 1
                cout << d << '\n';
                return 0;
            }
            int step = P[u];
            int posu = B[u];

            // enumerate reachable positions x = posu +/- k*step
            // cost increases by k (number of jumps)
            // go right
            ll k = 1;
            for (ll x = (ll)posu + step; x < N; x += step, ++k) {
                ll nd = d + k;
                if (step <= Bsq) {
                    int id2 = idx_small((int)x, step);
                    if (dist_small[id2] > nd) {
                        dist_small[id2] = nd;
                        pq.emplace(nd, 0, (int)x, step);
                    }
                }
                // if any doge at x, we can pass to it
                for (int doge : pos_at[x]) {
                    if (dist_doge[doge] > nd) {
                        dist_doge[doge] = nd;
                        pq.emplace(nd, 1, doge, 0);
                    }
                }
            }
            // go left
            k = 1;
            for (ll x = (ll)posu - step; x >= 0; x -= step, ++k) {
                ll nd = d + k;
                if (step <= Bsq) {
                    int id2 = idx_small((int)x, step);
                    if (dist_small[id2] > nd) {
                        dist_small[id2] = nd;
                        pq.emplace(nd, 0, (int)x, step);
                    }
                }
                for (int doge : pos_at[x]) {
                    if (dist_doge[doge] > nd) {
                        dist_doge[doge] = nd;
                        pq.emplace(nd, 1, doge, 0);
                    }
                }
            }
        }
    }

    // if never reached doge 1
    if (dist_doge[1] == INF) cout << -1 << '\n';
    else cout << dist_doge[1] << '\n';
    return 0;
}

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