Submission #635292

#	Time	Username	Problem	Language	Result	Execution time	Memory
635292		ljuba	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	182 ms	68080 KiB

skyscraper

#include <bits/stdc++.h>
#include <queue>
#include <vector>

using namespace std;

using ll = long long;

const int INF = 1e9 + 12;

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;

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

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

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

    for(int i = 0; i < n; ++i) {
        for(auto z : where[i]) {
            if(z.second == 0) continue;

            for(int j = 1; j < n; ++j) {
                int nx = j * z.second + i;

                if(nx >= n) break;

                adj[i].push_back({nx, j});

                if(where[nx].count({nx, z.second})) break;
            }

            for(int j = 1; j < n; ++j) {
                int nx = -j * z.second + i;

                if(nx < 0) break;

                adj[i].push_back({nx, j});

                if(where[nx].count({nx, z.second})) break;
            }
        }
    }

    // for(int i = 0; i < n; ++i) {
    //     cerr << i << ": ";
    //     for(auto z : adj[i]) {
    //         cerr << "{" << z.first << ", " << z.second << "}";
    //         cerr << ", ";
    //     }

    //     cerr << endl;
    // }

    auto calc = [&](int start, int end) {
        vector<int> dist(n, INF);

        dist[start] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

        pq.push({0, start});

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

            if(dist[tren.second] != tren.first) continue;

            for(auto e : adj[tren.second]) {
                if(dist[e.first] > dist[tren.second] + e.second) {
                    dist[e.first] = dist[tren.second] + e.second;
                    pq.push({dist[e.first], e.first});
                }
            }
        }

        return dist[end];
    };

    int ans = calc(v[0].first, v[1].first);

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

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