제출 #1054191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054191		Halym2007	밀림 점프 (APIO21_jumps)	C++17	37 / 100	4080 ms	24796 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;
int n, dis[N];
vector <int> v[N];
bool vis[N];
int vis1[N];
bool tt = 0;
bool cycle = 0;

void dfs (int x) {
	vis1[x] = 1;
	for (int i : v[x]) {
		if (vis1[i] == 1) {
			cycle = 1;
		}
		if (vis1[i]) continue;
		dfs (i);
	}
	vis1[x] = 2;
}

void init(int N, vector<int> H) {	
	n = N;
	stack <int> s;
	for (int i = 0; i < n; ++i) {
		if (H[i] != i + 1) {
			tt = 1;
		}
		while (!s.empty() and H[s.top()] <= H[i]) {
			s.pop();
		}
		if (!s.empty()) {
			v[i].pb (s.top());
		}
		s.push(i);
	}
	while (!s.empty()) s.pop();
	
	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() and H[s.top()] <= H[i]) {
			s.pop();
		}
		if (!s.empty()) {
			v[i].pb (s.top());
		}
		s.push(i);
	}
	
	for (int i = 0; i < n; ++i) {
		if (vis1[i]) continue;
		dfs (i);
	}
	assert (cycle == 0);
}

int minimum_jumps(int A, int B, int C, int D) {
	if (!tt) return C - B;
	for (int i = 0; i < n; ++i) {
 		vis[i] = 0;
 		dis[i] = 1e9;
	}
	queue <int> q;
	for (int i = A; i <= B; ++i) {
		q.push(i);
		vis[i] = 1;
		dis[i] = 0;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i : v[x]) {
			if (vis[i]) continue;
			q.push(i);
			dis[i] = dis[x] + 1;
			vis[i] = 1;
			if (i >= C and i <= D) {
				return dis[i];
			}
		}
	}
	return -1;
}



//int main() {
//	freopen ("input.txt", "r", stdin);
//  int N, Q;
//  assert(2 == scanf("%d %d", &N, &Q));
//  std::vector<int> H(N);
//  for (int i = 0; i < N; ++i) {
//    assert(1 == scanf("%d", &H[i]));
//  }
//  init(N, H);
//
//  for (int i = 0; i < Q; ++i) {
//    int A, B, C, D;
//    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
//    printf("%d\n", minimum_jumps(A, B, C, D));
//  }
//  return 0;
//}

• Subtask 1: 4 / 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