Submission #1195360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195360		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <limits>

using namespace std;

bool cmpPair(const pair<int,int> &a, const pair<int,int> &b) {
    return a.first > b.first;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> B(M), P(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> P[i];
    }

    int K = static_cast<int>(sqrt(N)) + 1;

    vector<bool> smallFlag(K + 1, false);
    for (int i = 0; i < M; ++i) {
        if (P[i] <= K) {
            smallFlag[P[i]] = true;
        }
    }

    vector<int> smallPs;
    for (int p = 1; p <= K; ++p) {
        if (smallFlag[p]) {
            smallPs.push_back(p);
        }
    }

    // bucket[p][r] = list of doge indices j with B[j] % p == r
    vector< vector< vector<int> > > bucket(K + 1);
    for (int pi : smallPs) {
        bucket[pi].assign(pi, vector<int>());
    }
    for (int j = 0; j < M; ++j) {
        for (int pi : smallPs) {
            int r = B[j] % pi;
            bucket[pi][r].push_back(j);
        }
    }

    // map of building -> doges initially there
    vector< vector<int> > building2doge(N);
    for (int j = 0; j < M; ++j) {
        building2doge[B[j]].push_back(j);
    }

    const int INF = numeric_limits<int>::max() / 2;
    vector<int> dist(M, INF);
    vector<bool> visited(M, false);

    // for small P, track which (p,r) we've scanned
    vector< vector<bool> > usedSmall(K + 1);
    for (int pi : smallPs) {
        usedSmall[pi].assign(pi, false);
    }

    priority_queue< pair<int,int>, vector<pair<int,int>>, decltype(&cmpPair) > pq(cmpPair);
    dist[0] = 0;
    pq.push(make_pair(0, 0));

    while (!pq.empty()) {
        pair<int,int> cur = pq.top();
        pq.pop();
        int d = cur.first;
        int i = cur.second;
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        if (i == 1) {
            break;
        }

        int bi = B[i];
        int pi = P[i];

        if (pi <= K) {
            int r = bi % pi;
            if (!usedSmall[pi][r]) {
                usedSmall[pi][r] = true;
                vector<int> &grp = bucket[pi][r];
                for (int j : grp) {
                    if (!visited[j]) {
                        int w = abs(B[j] - bi) / pi;
                        int nd = d + w;
                        if (nd < dist[j]) {
                            dist[j] = nd;
                            pq.push(make_pair(nd, j));
                        }
                    }
                }
                // clear to save memory
                grp.clear();
            }
        } else {
            int step = 1;
            int pos = bi + pi;
            while (pos < N) {
                int w = step;
                for (int j : building2doge[pos]) {
                    if (!visited[j]) {
                        int nd = d + w;
                        if (nd < dist[j]) {
                            dist[j] = nd;
                            pq.push(make_pair(nd, j));
                        }
                    }
                }
                ++step;
                pos += pi;
            }
            step = 1;
            pos = bi - pi;
            while (pos >= 0) {
                int w = step;
                for (int j : building2doge[pos]) {
                    if (!visited[j]) {
                        int nd = d + w;
                        if (nd < dist[j]) {
                            dist[j] = nd;
                            pq.push(make_pair(nd, j));
                        }
                    }
                }
                ++step;
                pos -= pi;
            }
        }
    }

    if (dist[1] >= INF) {
        cout << -1;
    } else {
        cout << dist[1];
    }
    return 0;
}

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