Submission #1208654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208654		k1r1t0	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	586 ms	113744 KiB

jumps

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 210000;
const int LOGN = 20;

int n, h[N], l[N], r[N], p1[N], p2[N], p3[N], d1[N], d2[N], jmp1[N][LOGN], jmp2[N][LOGN], jmp3[N][LOGN], ti[N], to[N], tc;
vector<int> cand_l[N], cand_r[N], g1[N], g2[N], g3[N];

void dfs1(int v) {
	d1[v] = (p1[v] == -1 ? 0 : d1[p1[v]] + 1);
	jmp1[v][0] = (p1[v] == -1 ? v : p1[v]);
	for (int k = 1; k < LOGN; k++)
		jmp1[v][k] = jmp1[jmp1[v][k - 1]][k - 1];
	ti[v] = to[v] = v;
	for (int u : g1[v]) {
		dfs1(u);
		ti[v] = min(ti[v], ti[u]);
		to[v] = max(to[v], to[u]);
	}
}

void dfs2(int v) {
	d2[v] = (p2[v] == -1 ? 0 : d2[p2[v]] + 1);
	jmp2[v][0] = (p2[v] == -1 ? v : p2[v]);
	for (int k = 1; k < LOGN; k++)
		jmp2[v][k] = jmp2[jmp2[v][k - 1]][k - 1];
	for (int u : g2[v])
		dfs2(u);
}

void dfs3(int v) {
	jmp3[v][0] = (p3[v] == -1 ? v : p3[v]);
	for (int k = 1; k < LOGN; k++)
		jmp3[v][k] = jmp3[jmp3[v][k - 1]][k - 1];
	for (int u : g3[v])
		dfs3(u);
}

void init(int N, vector<int> H) {
	n = N;
	for (int i = 1; i <= n; i++)
		h[i] = H[i - 1];
	stack<int> st;
	for (int i = 1; i <= n; i++)
		l[i] = r[i] = -1;
	for (int i = 1; i <= n; i++) {
		while (!st.empty() && h[st.top()] < h[i]) {
			r[st.top()] = i;
			st.pop();
		}
		if (!st.empty())
			l[i] = st.top();
		st.push(i);
	}
	for (int i = 1; i <= n; i++) {
		if (l[i] != -1)
			cand_r[l[i]].push_back(i);
		if (r[i] != -1)
			cand_l[r[i]].push_back(i);
		p1[i] = p2[i] = -1;
		p3[i] = r[i];
		if (p3[i] != -1)
			g3[p3[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		sort(begin(cand_l[i]), end(cand_l[i]), [&](int i, int j) {return h[i] > h[j];});
		sort(begin(cand_r[i]), end(cand_r[i]), [&](int i, int j) {return h[i] > h[j];});
		if (!cand_l[i].empty()) {
			int v = cand_l[i][0];
			g1[i].push_back(v);
			p1[v] = i;
			if (l[v] != -1) {
				g2[l[v]].push_back(v);
				p2[v] = l[v];
			}
		}
		if (!cand_r[i].empty()) {
			int v = cand_r[i][0];
			g1[i].push_back(v);
			p1[v] = i;
			if (r[v] != -1) {
				g2[r[v]].push_back(v);
				p2[v] = r[v];
			}
		}
	}
	tc = 0;
	for (int i = 1; i <= n; i++) {
		if (p1[i] == -1) dfs1(i);
		if (p2[i] == -1) dfs2(i);
		if (p3[i] == -1) dfs3(i);
	}
}

bool is_anc(int a, int b) {
	return ti[a] <= b && b <= to[a];
}

int solve(int a, int b) {
	int ans = 0;
	for (int k = LOGN - 1; k >= 0; k--)
		if (d2[a] - (1 << k) >= 0 && d1[jmp2[a][k]] >= d1[b]) {
			ans += (1 << k);
			a = jmp2[a][k];
		}
	for (int k = LOGN - 1; k >= 0; k--)
		if (d1[a] - (1 << k) >= 0 && d1[jmp1[a][k]] >= d1[b]) {
			ans += (1 << k);
			a = jmp1[a][k];
		}
	return ans;
}

int lca(int a, int b) {
	if (d1[a] < d1[b])
		swap(a, b);
	for (int k = LOGN - 1; k >= 0; k--)
		if (d1[a] - (1 << k) >= d1[b])
			a = jmp1[a][k];
	if (a == b)
		return a;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jmp1[a][k] != jmp1[b][k]) {
			a = jmp1[a][k];
			b = jmp1[b][k];
		}
	return p1[a];
}

int minimum_jumps(int a, int b, int c, int d) {
	a++; b++; c++; d++;
	int ta = max(a, ti[lca(c, d)]), tb = b;
	if (tb < ta) return -1;
	ta = lca(ta, tb);
	int tt = ta;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jmp3[tt][k] < c)
			tt = jmp3[tt][k];
	tt = p3[tt];
	if (tt < c || d < tt) return -1;
	int x = solve(ta, tt);
	if (l[tt] == -1 || r[l[tt]] == -1) return x;
	tt = r[l[tt]];
	if (tt < c || d < tt) return x;
	int y = solve(ta, tt);
	if (x == -1) return y;
	if (y == -1) return x;
	return min(x, y);
}

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