Submission #971151

#	Time	Username	Problem	Language	Result	Execution time	Memory
971151		dubabuba	Rainforest Jumps (APIO21_jumps)	C++14	4 / 100	693 ms	16780 KiB

jumps

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

using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2e5 + 10;
vector<int> adj[mxn];
int dis[mxn], h[mxn];
bool gay = 1;

void init(int N, vector<int> H) {
	vector<int> L(N, -1), R(N, -1);
	stack<int> st; st.push(0);
	for(int i = 1; i < N; i++) {
		while(st.size() && H[st.top()] <= H[i])
			st.pop();
		if(st.size())
			L[i] = st.top();
		st.push(i);
	}

	stack<int> en; en.push(0);
	for(int i = N - 1; i >= 0; i--) {
		while(en.size() && H[en.top()] <= H[i])
			en.pop();
		if(en.size())
			R[i] = en.top();
		en.push(i);
	}

	for(int i = 0; i < N; i++) {
		h[i] = H[i];
		if(L[i] > -1) adj[i].push_back(L[i]);
		if(R[i] > -1) adj[i].push_back(R[i]);
	}

	for(int i = 1; i < N; i++)
		if(H[i] <= H[i - 1])
			gay = 0;
}

map<pii, int> mp;
int solve(int u, int v) {
	if(h[u] >= h[v]) return INT_MAX;
	auto it = mp.find(MP(u, v));
	if(it != mp.end()) return (*it).ss;

	int ret = INT_MAX;
	for(int t : adj[u])
		ret = min(ret, solve(t, v));
	return mp[MP(u, v)] = ret;
}

int minimum_jumps(int A, int B, int C, int D) {
	if(gay) return C - B;
	if(A == B && C == D) {
		int t = solve(A, C);
		return (t == INT_MAX) ? -1 : t;
	}

	memset(dis, -1, sizeof dis);
	priority_queue<pii> pq;
	for(int i = A; i <= B; i++) {
		pq.push(MP(0, i));
	}

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

		if(dis[u] > -1) continue;
		dis[u] = d;

		for(int v : adj[u])
			if(dis[v] == -1)
				pq.push(MP(-(d + 1), v));
	}

	int ans = INT_MAX;
	for(int i = C; i <= D; i++)
	if(dis[i] > -1)
		ans = min(ans, dis[i]);
	return (ans == INT_MAX) ? -1 : ans;
}

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