Submission #1184465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184465		alterio	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	436 ms	52220 KiB

jumps

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

using namespace std;

const int mxn = 2e5 + 10, LOG = 18;

vector<int> g[mxn];
vector<int> H;
int N;
int high[mxn][LOG], low[mxn][LOG];
bool visited[mxn];

void dfs(int cur) {
	if (visited[cur]) return;
	visited[cur] = 1;
	if (cur >= N) return;
	for (auto x : g[cur]) dfs(x);
	low[cur][0] = g[cur][0];
	high[cur][0] = g[cur][1];
	for (int i = 1; i < LOG; i++) {
		low[cur][i] = low[low[cur][i - 1]][i - 1];
		high[cur][i] = high[high[cur][i - 1]][i - 1];
	}
}

void init(int _N, vector<int> _H) {
	N = _N, H = _H;
	for (int i = 0; i < LOG; i++) low[N][i] = high[N][i] = N;
	int mx = 0, pos = 0;
	for (int i = 0; i < N; i++) {
		if (H[i] > mx) {
			mx = H[i];
			pos = i;
		}
 	}
	H.push_back(1e9);
	stack<int> s;
	s.push(0);
	for (int i = 1; i < N; i++) {
		while (s.size() && H[i] > H[s.top()]) s.pop();
		if (s.size()) g[i].push_back(s.top());
		s.push(i);
	}
	while (s.size()) s.pop();
	s.push(N - 1);
	for (int i = N - 2; i >= 0; i--) {
		while (s.size() && H[i] > H[s.top()]) s.pop();
		if (s.size()) g[i].push_back(s.top());
		s.push(i);
	}
	for (int i = 0; i < N; i++) {
		if (g[i].size() == 2 && H[g[i][0]] > H[g[i][1]]) swap(g[i][0], g[i][1]);
		if (g[i].size() == 1) g[i].push_back(g[i][0]);
		while (g[i].size() < 2) g[i].push_back(N);
	}
	for (int i = 0; i < N; i++) dfs(i);
}

int minimum_jumps(int A, int B, int C, int D) { 
	int ans = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		if (H[high[A][i]] <= H[C]) {
			A = high[A][i];
			ans += 1 << i;
		}
	}
	for (int i = LOG - 1; i >= 0; i--) {
		if (H[low[A][i]] <= H[C]) {
			A = low[A][i];
			ans += 1 << i;
		}
	}
	return (H[A] == H[C] ? ans : -1);
}

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