제출 #1195018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195018		ainunnajib	Rainforest Jumps (APIO21_jumps)	C++20	37 / 100	4034 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
#include <numeric>       // Required potentially, though not used in final version

// Global variables
int N_global;
std::vector<int> H_global;
std::vector<int> L, R;
std::vector<std::vector<int>> rev_adj;
// Flag to check if the input matches the specific conditions of Subtask 1
bool is_subtask1 = false;

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

/**
 * @brief Helper function to check if the height array corresponds to Subtask 1.
 * In Subtask 1, H[i] = i + 1 for all i from 0 to N-1.
 * Complexity: O(N)
 *
 * @param N The number of trees.
 * @param H The vector containing tree heights.
 * @return True if H[i] = i + 1 for all i, False otherwise.
 */
bool check_subtask1(int N, const std::vector<int>& H) {
    if (H.size() != N) return false; // Basic sanity check
    for (int i = 0; i < N; ++i) {
        // The problem statement defines heights starting from 1.
        // H[i] = i + 1 means heights are 1, 2, 3, ..., N.
        if (H[i] != i + 1) {
            return false; // If any height doesn't match, it's not Subtask 1
        }
    }
    // If all heights match H[i] = i + 1, it's Subtask 1
    return true;
}

/**
 * @brief Preprocessing function called once before any queries.
 *
 * Checks if the input matches Subtask 1.
 * If not Subtask 1, calculates jump targets (L[i], R[i]) using monotonic stacks
 * and builds the reversed graph representation.
 * Complexity: O(N)
 *
 * @param N The number of trees.
 * @param H A vector containing the heights of the N trees.
 */
void init(int N, std::vector<int> H) {
    N_global = N;
    H_global = H;
    L.assign(N, -1);
    R.assign(N, -1);
    rev_adj.assign(N, std::vector<int>());

    // Check for the Subtask 1 special case (H[i] = i + 1)
    is_subtask1 = check_subtask1(N, H);

    // If it is Subtask 1, we can skip the general L, R, and rev_adj computation
    // because minimum_jumps can compute the answer directly in O(1).
    if (is_subtask1) {
        return;
    }

    // --- Calculate L[i] (nearest taller tree to the left) --- Not needed if Subtask 1
    std::stack<int> st_left;
    for (int i = 0; i < N; ++i) {
        while (!st_left.empty() && H[st_left.top()] <= H[i]) {
            st_left.pop();
        }
        if (!st_left.empty()) {
            L[i] = st_left.top();
        }
        st_left.push(i);
    }

    // --- Calculate R[i] (nearest taller tree to the right) --- Not needed if Subtask 1
    std::stack<int> st_right;
    for (int i = N - 1; i >= 0; --i) {
        while (!st_right.empty() && H[st_right.top()] <= H[i]) {
            st_right.pop();
        }
        if (!st_right.empty()) {
            R[i] = st_right.top();
        }
        st_right.push(i);
    }

    // --- Build the reversed graph `rev_adj` --- Not needed if Subtask 1
    for (int i = 0; i < N; ++i) {
        if (L[i] != -1) {
            rev_adj[L[i]].push_back(i);
        }
        if (R[i] != -1) {
            rev_adj[R[i]].push_back(i);
        }
    }
}

/**
 * @brief Calculates the minimum number of jumps required.
 *
 * Handles Subtask 1 (H[i]=i+1) as a special case for O(1) query time.
 * For other cases, uses the O(N) backward BFS approach per query.
 *
 * @param A Start index of the starting range [A, B].
 * @param B End index of the starting range [A, B].
 * @param C Start index of the ending range [C, D].
 * @param D End index of the ending range [C, D].
 * @return The minimum number of jumps, or -1 if impossible.
 */
int minimum_jumps(int A, int B, int C, int D) {
    // --- Handle Subtask 1 Special Case ---
    if (is_subtask1) {
        // In this case, jumps are always i -> i+1.
        // The graph is a simple path 0 -> 1 -> ... -> N-1.
        // The distance dist(s, e) is simply e - s (if s <= e).
        // We need min(e - s) for s in [A, B] and e in [C, D].
        // Since the problem guarantees B < C, we always have s <= B < C <= e, so s < e.
        // To minimize e - s, we maximize s (take s = B) and minimize e (take e = C).
        // The minimum number of jumps is C - B.
        return C - B;
    }

    // --- General Case: Backward BFS ---
    // (This part remains O(N) per query and is likely too slow for large N/Q in subtasks 5, 6, 7)
    std::vector<int> d(N_global, INF);
    std::queue<int> q;

    // Initialize BFS from the target range [C, D]
    for (int i = C; i <= D; ++i) {
        if (d[i] == INF) {
            d[i] = 0;
            q.push(i);
        }
    }

    // Perform BFS on the reversed graph
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : rev_adj[u]) { // Explore nodes 'v' that can jump TO 'u'
            if (d[v] == INF) {     // If 'v' is unvisited
                d[v] = d[u] + 1;   // Update distance
                q.push(v);         // Add to queue
            }
        }
    }

    // Find the minimum distance from the starting range [A, B]
    int min_jumps = INF;
    for (int i = A; i <= B; ++i) {
        if (d[i] != INF) { // Check if reachable
            min_jumps = std::min(min_jumps, d[i]);
        }
    }

    // Return result
    if (min_jumps == INF) {
        return -1; // Impossible
    } else {
        return min_jumps; // Minimum jumps found
    }
}

• Subtask 1: 4 / 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