Submission #725925

#	Time	Username	Problem	Language	Result	Execution time	Memory
725925		SanguineChameleon	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	4093 ms	9660 KiB

jumps

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

const int maxN = 2e5 + 20;
pair<int, int> range[maxN];
int par[maxN];
int pos[maxN];
int ch[maxN][2];
int H[maxN];
int N;
int node_cnt;
int A, B, C, D;
int start, fin;
int time_in[maxN];
int time_out[maxN];
int jump[maxN];
int T;

int dfs1(int lt, int rt) {
	if (lt > rt) {
		return -1;
	}
	int u = node_cnt++;
	range[u] = {lt, rt};
	pair<int, int> mx = {H[lt], lt};
	for (int i = lt; i <= rt; i++) {
		mx = max(mx, make_pair(H[i], i));
	}
	int mt = mx.second;
	pos[u] = mt;
	ch[u][0] = dfs1(lt, mt - 1);
	ch[u][1] = dfs1(mt + 1, rt);
	if (ch[u][0] != -1) {
		par[ch[u][0]] = u;
	}
	if (ch[u][1] != -1) {
		par[ch[u][1]] = u;
	}
	return u;
}

void dfs4(int u, int cur_0, int cur_1) {
	time_in[u] = ++T;
	if (ch[u][0] != -1) {
		jump[ch[u][0]] = cur_1;
		dfs4(ch[u][0], u, cur_1);
	}
	if (ch[u][1] != -1) {
		jump[ch[u][1]] = cur_0;
		dfs4(ch[u][1], cur_0, u);
	}
	time_out[u] = ++T;
}

bool anc(int u, int v) {
	return (u != -1 && v != -1) && (time_in[u] <= time_in[v] && time_out[v] <= time_out[u]);
}


void init(int _N, vector<int> _H) {
	N = _N;
	for (int i = 0; i < N; i++) {
		H[i] = _H[i];
	}
	dfs1(0, N - 1);
	dfs4(0, -1, -1);
}

void dfs3(int u) {
	if (u == -1) {
		return;
	}
	int mt = pos[u];
	if (B < mt) {
		dfs3(ch[u][0]);
	}
	else if (A > mt) {
		dfs3(ch[u][1]);
	}
	else {
		start = u;
		return;
	}
}

void dfs2(int u) {
	if (u == -1) {
		return;
	}
	int mt = pos[u];
	if (D < mt) {
		dfs2(ch[u][0]);
	}
	else if (C > mt) {
		dfs2(ch[u][1]);
	}
	else {
		fin = u;
		dfs3(u);
	}
}

int minimum_jumps(int _A, int _B, int _C, int _D) {
	A = _A;
	B = _B;
	C = _C;
	D = _D;
	start = -1;
	fin = -1;
	dfs2(0);
	if (start == -1 || fin == -1) {
		return -1;
	}
	int cur = start;
	int res = 0;
	while (D < pos[cur] || C > pos[cur]) {
		if ((D < pos[par[cur]] || C > pos[par[cur]]) && anc(fin, jump[cur])) {
			cur = jump[cur];
		}
		else {
			cur = par[cur];
		}
		res++;
	}
	return res;
}

• 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