Submission #1125105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125105		SamueleVid	Rainforest Jumps (APIO21_jumps)	C++20	21 / 100	4050 ms	15256 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N;
vector<int> H;
vector<vector<int>> adj;

void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;
    adj.resize(N);
    for (int i = 0; i < N; i ++) {
        for (int j = i - 1; j >= 0; j --) {
            if (H[j] > H[i]) {
                adj[i].push_back(j);
                break;
            }
        }
        for (int j = i + 1; j < N; j ++) {
            if (H[j] > H[i]) {
                adj[i].push_back(j);
                break;
            }
        }
    }

    // for (int i = 0; i < N; i ++) {
    //     cout << "i " << i << " : ";
    //     for (auto x : adj[i]) cout << x << " ";
    //     cout << '\n';
    // }
}

int minimum_jumps(int A, int B, int C, int D) {
    vector<int> v(N);
    vector<int> d(N, 1e9);
    queue<int> q;
    for (int i = A; i <= B; i ++) {
        q.push(i);
        d[i] = 0;
        v[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto x : adj[u]) {
            if (v[x]) continue;
            d[x] = d[u] + 1;
            v[x] = 1;
            q.push(x);
        }
    }

    int res = 1e9;
    for (int i = C; i <= D; i ++) res = min(res, d[i]);
    if (res == 1e9) res = -1;
    return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19