Submission #495927

#	Time	Username	Problem	Language	Result	Execution time	Memory
495927		FairyWinx	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1064 ms	109636 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<vector<int>> who(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 < m; ++i) {
        int a, b;
        cin >> a >> b;
        who[a].push_back(b);
        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.first) {
            cout << dist[v][p] << '\n';
            return 0;
        }
        used2[v][p] = 1;
        if (!used1[v]) {
            used1[v] = 1;
            for (int i : who[v]) {
                dist[v][i] = dist[v][p];
                q.push({dist[v][i], {v, i}});
            }
        }
        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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43