제출 #1223471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223471		Jer	밀림 점프 (APIO21_jumps)	C++20	21 / 100	1608 ms	2732 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int MAXN = 100005;
pair<int, int> con[MAXN];
int n;

bool vis[MAXN];

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

	for (int i = 0; i < n; i++)
	{
		con[i].first = -1, con[i].second = -1;
		for (int j = i + 1; j < n; j++){
			if (H[i] < H[j])
				{con[i].second = j; break;}
		}

		for (int j = i - 1; j >= 0; j--){
			if (H[i] < H[j])
				{con[i].first = j; break;}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	for (int i = 0; i < n; i++)
	vis[i] = false;

	queue<int> q;

	for (int s = A; s <= B; s++)
		q.push(s);

	int l = 0, curr, len;

	while (!q.empty())
	{
		len = q.size();
		for (int z = len; z > 0; z--){
			curr = q.front(), q.pop();

			if (vis[curr])
				continue;
			vis[curr] = true;

			if (curr >= C and curr <= D)
				return l;

			if (con[curr].first != -1)
				q.push(con[curr].first);

			if (con[curr].second != -1)
				q.push(con[curr].second);
		}
		l++;
	}

	return -1;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19