Submission #1195013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195013		ainunnajib	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4094 ms	16776 KiB

jumps

#include <vector>        // For std::vector
#include <queue>         // For std::queue
#include <stack>         // For std::stack
#include <algorithm>     // For std::min
#include <limits>        // For std::numeric_limits

// Global variables to store tree information and precomputed data
int N_global;              // Number of trees
std::vector<int> H_global; // Heights of the trees

// L[i]: index of the nearest tree to the left of 'i' with height > H[i]. -1 if no such tree exists. [cite: 5]
// R[i]: index of the nearest tree to the right of 'i' with height > H[i]. -1 if no such tree exists. [cite: 6]
std::vector<int> L, R;

// Reversed graph adjacency list. [cite: 5, 6]
// rev_adj[j] contains all indices 'i' such that the orangutan can jump FROM 'i' TO 'j'.
// This is used for the backward BFS.
std::vector<std::vector<int>> rev_adj;

// Define a constant for infinity, used for unreachable nodes in BFS.
const int INF = std::numeric_limits<int>::max();

/**
 * @brief Preprocessing function called once before any queries.
 *
 * Calculates the possible jump destinations (L[i] and R[i]) for each tree 'i'
 * using monotonic stacks.
 * Builds the reversed graph representation needed for backward BFS.
 * Complexity: O(N)
 *
 * @param N The number of trees. [cite: 9]
 * @param H A vector containing the heights of the N trees. [cite: 10]
 */
void init(int N, std::vector<int> H) {
    N_global = N;
    H_global = H; // Store N and H globally for access in minimum_jumps
    L.assign(N, -1); // Initialize left jump targets to -1 (no jump)
    R.assign(N, -1); // Initialize right jump targets to -1
    rev_adj.assign(N, std::vector<int>()); // Initialize the reversed adjacency list

    // --- Calculate L[i] (nearest taller tree to the left) ---
    std::stack<int> st_left; // Monotonic stack storing indices in decreasing height order
    for (int i = 0; i < N; ++i) {
        // Pop elements from the stack that are shorter than or equal to the current tree H[i]
        // Ensures the stack top (if exists) is the nearest element to the left *taller* than H[i]
        while (!st_left.empty() && H[st_left.top()] <= H[i]) {
            st_left.pop();
        }
        // If the stack is not empty, the top element is the target L[i]
        if (!st_left.empty()) {
            L[i] = st_left.top();
        }
        // Push the current tree index onto the stack
        st_left.push(i);
    }

    // --- Calculate R[i] (nearest taller tree to the right) ---
    std::stack<int> st_right; // Monotonic stack
    for (int i = N - 1; i >= 0; --i) { // Iterate from right to left
        // Pop elements shorter than or equal to H[i]
        while (!st_right.empty() && H[st_right.top()] <= H[i]) {
            st_right.pop();
        }
        // If stack not empty, top is the target R[i]
        if (!st_right.empty()) {
            R[i] = st_right.top();
        }
        // Push current index
        st_right.push(i);
    }

    // --- Build the reversed graph adjacency list `rev_adj` ---
    // For each possible jump i -> L[i] or i -> R[i] in the original graph,
    // add a corresponding reversed edge L[i] -> i or R[i] -> i to rev_adj.
    for (int i = 0; i < N; ++i) {
        if (L[i] != -1) {
            // If a jump from i to L[i] is possible, add edge L[i] -> i in reversed graph
            rev_adj[L[i]].push_back(i);
        }
        if (R[i] != -1) {
             // If a jump from i to R[i] is possible, add edge R[i] -> i in reversed graph
            rev_adj[R[i]].push_back(i);
        }
    }
}

/**
 * @brief Calculates the minimum number of jumps required.
 *
 * Finds the minimum jumps needed to get from any starting tree 's' in the range [A, B]
 * to any ending tree 'e' in the range [C, D]. [cite: 7, 8]
 * Uses Breadth-First Search (BFS) starting *backwards* from the target range [C, D]
 * on the reversed graph.
 * Complexity: O(N) per query, as BFS visits each node/edge at most once.
 *
 * @param A The start index of the starting range. [cite: 12]
 * @param B The end index of the starting range. [cite: 12]
 * @param C The start index of the ending range. [cite: 13]
 * @param D The end index of the ending range. [cite: 13]
 * @return The minimum number of jumps, or -1 if it's impossible. [cite: 14]
 */
int minimum_jumps(int A, int B, int C, int D) {
    // 'd[i]' will store the minimum jumps from tree 'i' to *any* tree in the range [C, D].
    std::vector<int> d(N_global, INF); // Initialize distances to infinity
    std::queue<int> q;                 // Queue for BFS

    // --- Initialize BFS ---
    // Start BFS from all trees in the target range [C, D].
    // Set their distance to 0 and add them to the queue.
    for (int i = C; i <= D; ++i) {
        // Check if already initialized (d[i] might be set if C=D and the node is added multiple times, though loop structure prevents this)
        if (d[i] == INF) {
            d[i] = 0; // Distance from a target node to the target set is 0
            q.push(i); // Add to BFS queue
        }
    }

    // --- Perform Backward BFS ---
    // Explore the graph using the reversed edges (rev_adj).
    while (!q.empty()) {
        int u = q.front(); // Current node being processed
        q.pop();

        // Iterate through all nodes 'v' that can jump *to* 'u' in the original graph
        // (represented by edges u -> v in the reversed graph)
        for (int v : rev_adj[u]) {
            // If node 'v' has not been reached yet (distance is INF)
            if (d[v] == INF) {
                // Update the distance to 'v' (one more jump than distance to 'u')
                d[v] = d[u] + 1;
                // Add 'v' to the queue to explore its predecessors
                q.push(v);
            }
        }
    }

    // --- Find the minimum jumps from the starting range [A, B] ---
    int min_jumps = INF; // Initialize minimum jumps found so far
    // Iterate through all possible starting trees 's' in the range [A, B]
    for (int i = A; i <= B; ++i) {
        // If tree 'i' can reach the target range (d[i] is not INF)
        if (d[i] != INF) {
            // Update the overall minimum jumps if the path from 'i' is shorter
            min_jumps = std::min(min_jumps, d[i]);
        }
    }

    // --- Return the result ---
    // If min_jumps is still INF, no path exists from [A, B] to [C, D]
    if (min_jumps == INF) {
        return -1; // Impossible [cite: 14, 21]
    } else {
        // Otherwise, return the minimum number of jumps found [cite: 8]
        return min_jumps;
    }
}

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