제출 #948429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948429		vjudge1	밀림 점프 (APIO21_jumps)	C++17	33 / 100	4024 ms	13920 KiB

jumps

#include "jumps.h"
//#include "stub.cpp"

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()


using namespace std;
const int N=2e5+5;
vector<int> g[N];
int n;
void init(int n_, vector<int> a){
	n=n_;
	stack<int> A;
	for(int i=0;i<n;i++){
		while(!A.empty() && a[A.top()]<a[i]) A.pop();
		if(!A.empty()) g[i].pb(A.top());
		A.push(i);
	}
	while(!A.empty()) A.pop();
	for(int i=n-1;i>=0;i--){
		while(!A.empty() && a[A.top()]<a[i]) A.pop();
		if(!A.empty()) g[i].pb(A.top());
		A.push(i);
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	queue< pair <int,int> > dq;
	vector<bool> used(n);
	for(int i=A;i<=B;i++){
		dq.push(make_pair(i,0));
	}
	int ans=1e9;
	while(!dq.empty()){
		int x=dq.front().fr;
		int d=dq.front().sc;
		dq.pop();
		if(C<=x && x<=D) ans=min(ans,d);
		for(auto it: g[x]){
			if(!used[it]){
				used[it]=1;
				dq.push(make_pair(it,d+1));
			}
		}
	}
	if(ans==1e9) ans=-1;
	//cout<<ans<<endl;
	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