Submission #586071

#	Time	Username	Problem	Language	Result	Execution time	Memory
586071		jairRS	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4075 ms	22180 KiB

jumps

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

const int INF = 1e9 + 1;
vector<int> firstGreaterToTheRight;
vector<vector<int>> adj;

void init(int N, vector<int> H)
{
	stack<pair<int, int>> s;
	firstGreaterToTheRight = vector<int>(N, -1);
	adj = vector<vector<int>>(N);
	for (int i = N - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top().first < H[i])
			s.pop();

		if (!s.empty())
			firstGreaterToTheRight[i] = s.top().second;

		s.push({H[i], i});
	}

	for (int i = 0; i < N; i++)
		if (firstGreaterToTheRight[i] != -1)
			adj[firstGreaterToTheRight[i]].push_back(i);
}

int minimum_jumps(int A, int B, int C, int D)
{
	int res = INF;
	for (int R = C; R <= D; R++)
	{
		queue<pair<int, int>> bfs;
		map<int, bool> vis;
		bfs.push({R, 0});
		vis[R] = true;
		while (!bfs.empty())
		{
			pair<int, int> cur = bfs.front();
			bfs.pop();
			for (int a : adj[cur.first])
			{
				if (vis[a])
					continue;
				bfs.push({a, cur.second + 1});
				if (A <= a && a <= B)
					res = min(res, cur.second + 1);
			}
		}
	}

	return (res == INF ? -1 : res);
}

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