제출 #1162752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162752		Malix	밀림 점프 (APIO21_jumps)	C++20	33 / 100	4066 ms	14564 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;\

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
const ll INF=1000000000000000010;
const int inf=1e9+10;
const ll M=1e9+7;

vii a;
int n;

void init(int N, std::vector<int> H) {
  n=N;
  a.resize(n);

  stack<pi> st;
  st.push({H[0],0});
  REP(i,1,n){
    if(st.top().F<H[i]){
      while(!st.empty()&&st.top().F<H[i]){
        a[st.top().S].PB(i);
        st.pop();
      }
    }
    st.push({H[i],i});
  }
  
  st=stack<pi>();
  st.push({H[n-1],n-1});
  for(int i=n-2;i>=0;i--){
    if(st.top().F<H[i]){
      while(!st.empty()&&st.top().F<H[i]){
        a[st.top().S].PB(i);
        st.pop();
      }
    }
    st.push({H[i],i});
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  vi vis(n,0),dis(n,inf);
  queue<int> q;
  REP(i,A,B+1){
    q.push(i);
    dis[i]=0;
  }
  while(!q.empty()){
    int x=q.front();
    q.pop();
    if(vis[x])continue;
    vis[x]=1;
    for(auto u:a[x]){
      if(!vis[u]){
        q.push(u);
        dis[u]=min(dis[u],dis[x]+1);
      }
    }
  }
  int ans=inf;
  REP(i,C,D+1)ans=min(ans,dis[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