Submission #495899

#	Time	Username	Problem	Language	Result	Execution time	Memory
495899		FairyWinx	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	324 KiB

skyscraper

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SOLVE int t; cin >> t; while (t--) solve();

#define int long long

using namespace std;

signed main() {
    #ifdef DEBUG
        freopen("main/in.txt", "r", stdin);
    #endif
    #ifndef LOCAL
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    #endif

    int n, m;
    cin >> n >> m;
    vector<map<int, int>> d(n);
    vector<map<int, int>> dist(n);
    pair<int, int> to;
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        d[a][b] = 0;
        if (i == 0) {
            dist[a][b] = 0;
            q.push({0, {a, b}});
        } else if (i == 1) {
            to = {a, b};
        }
    }
    vector<int> used1(n);
    vector<map<int, int>> used2(n);
    while (q.size()) {
        auto [v, p] = q.top().second;
        q.pop();
        if (used2[v][p]) {
            continue;
        }
        if (v == to.second) {
            cout << dist[v][p] << '\n';
            return 0;
        }
        used2[v][p] = 1;
        if (!used1[v]) {
            used1[v] = 1;
            for (auto i : d[v]) {
                if (!dist[v].count(i.first) || dist[v][i.first] > i.second + dist[v][p]) {
                    dist[v][i.first] = i.second + dist[v][p];
                    q.push({dist[v][i.first], {v, i.first}});
                }
            }
        }
        if (v + p < n) {
            if (!dist[v + p].count(p) || dist[v + p][p] > dist[v][p] + 1) {
                dist[v + p][p] = dist[v][p] + 1;
                q.push({dist[v + p][p], {v + p, p}});
            }
        }
        if (v - p >= 0) {
            if (!dist[v - p].count(p) || dist[v - p][p] > dist[v][p] + 1) {
                dist[v - p][p] = dist[v][p] + 1;
                q.push({dist[v - p][p], {v - p, p}});
            }
        }
    }
    cout << -1 << '\n';
}

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