제출 #725951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725951		SanguineChameleon	밀림 점프 (APIO21_jumps)	C++17	33 / 100	4090 ms	66040 KiB

jumps

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

const int maxN = 2e5 + 20;
const int maxL = 20;
int lg[maxN];
pair<int, int> range[maxN];
pair<int, int> sparse[maxN][maxL];
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][maxL];
int T;

int get(int lt, int rt) {
	int k = lg[rt - lt + 1];
	return max(sparse[lt][k], sparse[rt - (1 << k) + 1][k]).second;
}

int dfs1(int lt, int rt) {
	if (lt > rt) {
		return -1;
	}
	int u = node_cnt++;
	range[u] = {lt, rt};
	int mt = get(lt, rt);
	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]][0] = cur_1;
		dfs4(ch[u][0], u, cur_1);
	}
	if (ch[u][1] != -1) {
		jump[ch[u][1]][0] = 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) {
	for (int i = 2; i < maxN; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	N = _N;
	for (int i = 0; i < N; i++) {
		H[i] = _H[i];
		sparse[i][0] = {H[i], i};
	}
	for (int k = 1; k < maxL; k++) {
		for (int i = 0; i + (1 << k) <= N; i++) {
			sparse[i][k] = max(sparse[i][k - 1], sparse[i + (1 << (k - 1))][k - 1]);
		}
	}
	dfs1(0, N - 1);
	dfs4(0, -1, -1);
	jump[0][0] = -1;
	for (int k = 1; k < maxL; k++) {
		for (int u = 0; u < N; u++) {
			int v = jump[u][k - 1];
			if (v == -1) {
				jump[u][k] = v;
			}
			else {
				jump[u][k] = jump[v][k - 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 (C > pos[cur]) {
		if (C > pos[par[cur]] && anc(fin, jump[cur][0])) {
			cur = jump[cur][0];
		}
		else {
			break;
		}
		res++;
	}
	while (C > pos[cur]) {
		cur = par[cur];
		res++;
	}
	return res;
}

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