Submission #979418

#	Time	Username	Problem	Language	Result	Execution time	Memory
979418		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4073 ms	15780 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200100];
int vis[200100],d[200100],n,h[200100];
void init(int N, std::vector<int> H) {
    stack<int> stk;
    n=N;
    for(int i=0;i<N;i++){
        while(stk.size()&&H[stk.top()]<=H[i])   
            stk.pop();
        if(stk.size())
            adj[i].push_back(stk.top());
        stk.push(i);
    }
    while(stk.size())stk.pop();
    for(int i=N;i--;){
        while(stk.size()&&H[stk.top()]<=H[i])   
            stk.pop();
        if(stk.size())
            adj[i].push_back(stk.top());
        stk.push(i);
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    queue<int> q;
    for(int i=0;i<n;i++)
        vis[i]=0;
    for(int i=A;i<=B;i++)
        vis[i]=1,q.push(i),d[i]=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(auto i:adj[x]) if(!vis[i])
            vis[i]=1,d[i]=d[x]+1,q.push(i);
    }
    int ans=n;
    for(int i=C;i<=D;i++)
        if(vis[i])
            ans=min(ans,d[i]);
    return ans<n?ans:-1;
}

• 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