Submission #735556

#	Time	Username	Problem	Language	Result	Execution time	Memory
735556		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	121 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

int main() {
        int n, m;
        cin >> n >> m;
        vector<int> a(m), b(m);
        for (int i = 0; i < m; i++) cin >> a[i] >> b[i];
        int sn = sqrt(n * __lg(n)) + 1;
        vector<vector<int64_t>> d(n, vector<int64_t>(sn + 1, 9e18));
        vector<vector<vector<tuple<int, int, int>>>> adj(n, vector<vector<tuple<int, int, int>>>(sn + 1));

        for (int i = 0; i < m; i++) {
                if (b[i] < sn) {
                        adj[a[i]][sn].emplace_back(a[i], b[i], 0);
                } else {
                        for (int j = a[i] % b[i]; j < n; j += b[i]) {
                                adj[a[i]][sn].emplace_back(j, sn, abs(a[i] - j) / b[i]);
                        }
                }
        }

        d[a[0]][sn] = 0;
        priority_queue<tuple<int64_t, int, int>> pq;
        pq.emplace(0, a[0], sn);
        while (pq.size()) {
                auto [du, u, s] = pq.top();
                pq.pop();
                if (d[u][s] != -du) continue;
                du = -du;
                if (u == a[1]) return cout << du, 0;

                if (s != sn && u - s >= 0) {
                        int uu = u - s, ss = s, c = 1;
                        if (d[uu][ss] > du + c) {
                                d[uu][ss] = du + c;
                                pq.emplace(-d[uu][ss], uu, ss);
                        }
                        ss = sn;
                        if (d[uu][ss] > du + c) {
                                d[uu][ss] = du + c;
                                pq.emplace(-d[uu][ss], uu, ss);
                        }
                }

                if (s != sn && u + s < n) {
                        int uu = u + s, ss = s, c = 1;
                        if (d[uu][ss] > du + c) {
                                d[uu][ss] = du + c;
                                pq.emplace(-d[uu][ss], uu, ss);
                        }
                        ss = sn;
                        if (d[uu][ss] > du + c) {
                                d[uu][ss] = du + c;
                                pq.emplace(-d[uu][ss], uu, ss);
                        }
                }

                for (auto [uu, ss, c] : adj[u][s]) {
                        if (d[uu][ss] > du + c) {
                                d[uu][ss] = du + c;
                                pq.emplace(-d[uu][ss], uu, ss);
                        }
                }
        }
        cout << -1;
}

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