Submission #376037

#	Time	Username	Problem	Language	Result	Execution time	Memory
376037		Alma	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	889 ms	262148 KiB

skyscraper

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int minimumJumps (int l, int r, int start, int objective, vector<vector<int>> & skycrapers) {

    // make the bfs:
    int n = (int)skycrapers.size();
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>> queueBFS; // {jumps, position}
    queueBFS.push(make_pair(0, start));
    int jumps, idx;

    while (!queueBFS.empty()) {
        jumps = -queueBFS.top().first;
        idx = queueBFS.top().second;
        queueBFS.pop();

        // check if we arrived at pos1
        if (idx == objective) {
            return jumps;
        }
        visited[idx] = true;

        // visit all conections:
        for (int p: skycrapers[idx]) {
            if (p == 0) {
                continue; // this doge has null movement
            }
            // to the left:
            int left = idx - p;
            for (int i = 1; l <= left; i++) {
                if (!skycrapers[left].empty() && !visited[left]) {
                    queueBFS.push(make_pair(-(jumps+i), left));
                }
                left -= p;
            }
            // to the right:
            int right = idx + p;
            for (int i = 1; right <= r; i++) {
                if (!skycrapers[right].empty() && !visited[right]) {
                    queueBFS.push(make_pair(-(jumps+i), right));
                }
                right += p;
            }
        }
    }
    // if we arrive at here there is no possible path:
    return -1;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(NULL);
    
    // input:
    int n, m, x, p, pos0, pos1;
    cin >> n >> m;
    vector<vector<int>> skycrapers(n, vector<int>());

    // doge 0:
    cin >> x >> p;
    skycrapers[x].push_back(p);
    pos0 = x;

    // doge 1:
    cin >> x >> p;
    skycrapers[x].push_back(p);
    pos1 = x;

    // other doges:
    m -= 2;
    for (int i = 0; i < m; i++) {
        cin >> x >> p;
        skycrapers[x].push_back(p);
    }
    // call function:
    cout << minimumJumps(0, n-1, pos0, pos1, skycrapers) << '\n';

    return 0;
}

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