Submission #553540

#	Time	Username	Problem	Language	Result	Execution time	Memory
553540		Jarif_Rahman	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4073 ms	15948 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf  = 1e9;
int n;
vector<vector<int>> v;
vector<int> h;
vector<int> lg, rg;

void init(int n, vector<int> h){
    ::n = n, ::h = h;
    stack<int> st;
    v.resize(n);
    lg.resize(n, -1);
    rg.resize(n, -1);
    for(int i = 0; i < n; i++){
        while(!st.empty() && h[st.top()] < h[i]){
            int x = st.top(); st.pop();
            rg[x] = i;
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n-1; i >= 0; i--){
        while(!st.empty() && h[st.top()] < h[i]){
            int x = st.top(); st.pop();
            lg[x] = i;
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = 0; i < n; i++){
        if(lg[i] != -1){
            v[i].pb(lg[i]);
        }
        if(rg[i] != -1){
            v[i].pb(rg[i]);
        }
    }
}

int minimum_jumps(int a, int b, int c, int d){
    vector<int> dis(n, inf);
    vector<bool> bl(n, 0);
    queue<int> q;
    for(int i = a; i <= b; i++){
        q.push(i);
        bl[i] = 1;
        dis[i] = 0;
    }
    while(!q.empty()){
        int nd = q.front(); q.pop();
        for(int x: v[nd]){
            if(bl[x]) continue;
            bl[x] = 1;
            dis[x] = dis[nd]+1;
            q.push(x);
        }
    }
    int mn = inf;
    for(int i = c; i <= d; i++) mn = min(mn, dis[i]);
    if(mn >= inf) mn = -1;
    return mn;
}

• 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