Submission #634974

#	Time	Username	Problem	Language	Result	Execution time	Memory
634974		ljuba	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1088 ms	7680 KiB

skyscraper

#include <bits/stdc++.h>
#include <exception>

using namespace std;

using ll = long long;

const int INF = 1e9 + 12;

const int K = 120;

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

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> v(m);

    for(auto &z : v) cin >> z.first >> z.second;

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    pq.push({0, v[0]});

    set<pair<int, int>> visited;

    int ans = INF;

    vector<pair<int, int>> where[n];

    for(auto z : v) {
        where[z.first].push_back(z);
    }

    while(!pq.empty()) {
        auto best = pq.top();
        pq.pop();

        auto dist = best.first;
        auto current = best.second;

        if(visited.count(current)) continue;

        // cerr << dist << " " << current.first << " " << current.second << endl;

        if(current == v[1]) {
            ans = min(ans, dist);
            break;
        }

        visited.insert(current);
        // where[current.first].erase(current);

        if(current.second < K) {
            for(auto z : where[current.first]) {
                pq.push({dist, z});
            }

            if(current.second != 0) {
                vector<pair<int, int>> go;
                go.push_back({current.first - current.second, current.second});
                go.push_back({current.first + current.second, current.second});

                auto check = [&n](pair<int, int> x) {
                    return x.first >= 0 && x.first < n;
                };

                for(auto z : go) {
                    if(check(z)) {
                        pq.push({dist + 1, z});
                    }
                }
            }
        } else {
            for(int i = current.first % current.second; i < n; i += current.second) {
                int raz = abs(i - current.first);
                raz /= current.second;

                for(auto z : where[i]) {
                    pq.push({dist + raz, z});
                }
            }
        }
    }

    cout << ((ans >= INF) ? -1 : ans) << '\n';
}

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