Submission #568446

#	Time	Username	Problem	Language	Result	Execution time	Memory
568446		_karan_gandhi	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	307 ms	97828 KiB

jumps

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

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

int n;
vector<int> h;
vector<vector<int>> adj;
const int LOG = 20;
vector<vector<int>> hi, lo;

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

	hi = vector<vector<int>>(n, vector<int>(LOG));
	lo = vector<vector<int>>(n, vector<int>(LOG));

	stack<int> st;
	for (int i = 0; i < n; i++) {
		// cout << st.size() << endl;
		while (st.size() > 0 && h[st.top()] < h[i]) {
			st.pop();
		}
		if (st.size() != 0) adj[i].push_back(st.top());
		st.push(i);
	}

	while (st.size() != 0) st.pop();
	
	for (int i = n - 1; i >= 0; i--) {
		while (st.size() > 0 && h[st.top()] < h[i]) {
			st.pop();
		}
		if (st.size() != 0) adj[i].push_back(st.top());
		st.push(i);
	}

	// first build the lo
	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 0) {
			lo[i][0] = -1;
			continue;
		}
		int nxt = adj[i][0];
		for (int v : adj[i]) if (h[nxt] > h[v]) nxt = v;
		lo[i][0] = nxt;
	}

	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) {
			if (lo[j][i - 1] == -1) {
				lo[j][i] = -1;
				continue;
			}
			lo[j][i] = lo[lo[j][i - 1]][i - 1];
		}
	}

	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 0) {
			hi[i][0] = -1;
			continue;
		}
		int nxt = adj[i][0];
		for (int v : adj[i]) if (h[nxt] < h[v]) nxt = v;
		hi[i][0] = nxt;
	}

	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) {
			if (hi[j][i - 1] == -1) {
				hi[j][i] = -1;
				continue;
			}
			hi[j][i] = hi[hi[j][i - 1]][i - 1];
		}
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	assert(a == b && c == d);

	int pow = LOG - 1;
	int u = a;
	int t = c;
	int ans = 0;
	while (pow >= 0) {
		if (hi[u][pow] != -1 && h[hi[u][pow]] < h[t]) {
			u = hi[u][pow]; // keep taking the hi edge
			ans += (1 << pow);
		}
		pow--;
	}

	pow = LOG - 1;

	while (pow >= 0) {
		if (lo[u][pow] != -1 && h[lo[u][pow]] < h[t]) {
			u = lo[u][pow];
			ans += (1 << pow);
		}
		pow--;
	}
	if (lo[u][0] != t) return -1;

	return ans + 1;
}

• 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