Submission #1216486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216486		tapilyoca	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4030 ms	3476 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;


ll n;
vec<int> a;
void init(int N, std::vector<int> H) {
    n = N;
    a = H;
}

int minimum_jumps(int A, int B, int C, int D) {
    assert(A == B && C == D);

    vec<int> jumpRight(n, -1), jumpLeft(n, -1); // nearest greater right/left

    stack<int> st;
    for(int i = 0; i < n; ++i) {
        while(!st.empty() and a[st.top()] < a[i]) {
            jumpRight[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() and a[st.top()] < a[i]) {
            jumpLeft[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    vec<bool> vis(n,0);
    queue<pair<int, int>> q;
    q.push({A, 0});
    vis[A] = 1;

    while(!q.empty()) {
        pair<int,int> temp = q.front();
        q.pop();
        int u = temp.first;
        int dist = temp.second;
        if(u == C) return dist;

        if(jumpLeft[u] != -1 and !vis[jumpLeft[u]]) {
            vis[jumpLeft[u]] = 1;
            q.push({jumpLeft[u], dist+1});
        }

        if(jumpRight[u] != -1 and !vis[jumpRight[u]]) {
            vis[jumpRight[u]] = 1;
            q.push({jumpRight[u], dist+1});
        }
    }

    return -1; // unreachable
}

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