Submission #1162415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162415		brinton	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4094 ms	14500 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000
vector<vector<int>> edges;
vector<int> H;
int N;
void init(int iN, std::vector<int> iH) {
  N = iN;
  H = iH;
  // create DAG using monotic array
  stack<int> st;
  edges.resize(N+1);
  // create front
  for(int i = 0;i < N;i++){
    while(!st.empty() && st.top() < H[i]){
      st.pop();
    }
    
    if(!st.empty()){
      edges[H[i]].push_back(st.top());
    }
    st.push(H[i]);
  }

  while(!st.empty()) st.pop();
  // from back
  for(int i = N-1;i >= 0;i--){
    while(!st.empty() && st.top() < H[i]){
      st.pop();
    }
    
    if(!st.empty()){
      edges[H[i]].push_back(st.top());
    }
    st.push(H[i]);
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  vector<int> dist(N+1,inf);
  queue<int> q;
  for(int i = A;i <= B;i++){
    dist[H[i]] = 0;
    q.push(H[i]);
  }
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    for(auto nxt:edges[cur]){
      if(dist[nxt] == inf){
        dist[nxt] = dist[cur]+1;
        q.push(nxt);
      }
    }
  }
  int ans = inf;
  for(int i = C;i <= D;i++){
    ans = min(ans,dist[H[i]]);
  }
  if(ans == inf){
    return -1;
  }
  return ans;
}

• 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