oj.uz

Submission #495921

# Submission time Handle Problem Language Result Execution time Memory
495921 2021-12-20T07:53:49 Z FairyWinx Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 204 KB 
#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.second) {
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -