oj.uz

Submission #533873

# Submission time Handle Problem Language Result Execution time Memory
533873 2022-03-07T14:12:42 Z hollwo_pelw Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1155 ms 33168 KB 
#include "jumps.h"

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

const int N = 2e5 + 5;

int big_jmp[18][N], sml_jmp[18][N];
int h[N], ljmp[N], rjmp[N];

void init(int n, vector<int> a) {
	a.insert(a.begin(), n + 1); // to 1-based

	static int st[N];

	for (int i = 1, top = 0; i <= n; i++) {
		while (top && a[st[top]] < a[i])
			rjmp[st[top --]] = i;
		st[++ top] = i;
	}

	for (int i = n, top = 0; i >= 1; i--) {
		while (top && a[st[top]] < a[i])
			ljmp[st[top --]] = i;
		st[++ top] = i;
	}

	for (int i = 1; i <= n; i++) {
		big_jmp[0][i] = a[rjmp[i]] > a[ljmp[i]] ? rjmp[i] : ljmp[i];
		sml_jmp[0][i] = a[rjmp[i]] < a[ljmp[i]] ? rjmp[i] : ljmp[i];
	}

	for (int i = 1; i < 18; i++)
		for (int j = 1; j <= n; j++) {
			big_jmp[i][j] = big_jmp[i - 1][big_jmp[i - 1][j]];
			sml_jmp[i][j] = sml_jmp[i - 1][sml_jmp[i - 1][j]];
		}

	vector<int> ord(n);
	for (int i = 1; i <= n; i++)
		ord[n - a[i]] = i;

	for (auto u : ord)
		h[u] = h[sml_jmp[0][u]] + 1;
}

inline int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 18; i --; )
		if (h[v] - h[u] >> i & 1)
			v = sml_jmp[i][v];
	if (u == v) return u;
	for (int i = 18; i --; )
		if (sml_jmp[i][u] ^ sml_jmp[i][v])
			u = sml_jmp[i][u], v = sml_jmp[i][v];
	return sml_jmp[0][u];
}

int minimum_jumps(int a, int b, int c, int d) {
	++ a, ++ b, ++ c, ++ d; // to 1-based

	int u = lca(a, b), v = lca(c, d), res = 0;
	{
		int possible = lca(u, v);
		if (possible != v) return -1;
	}

	for (int i = 18; i --; )
		if (h[big_jmp[i][u]] >= h[v]) {
			res += 1 << i;
			u = big_jmp[i][u];
		}

	for (int i = 18; i --; )
		if (h[sml_jmp[i][u]] >= h[v] && sml_jmp[i][u] < c) {
			res += 1 << i;
			u = sml_jmp[i][u];
		}

	return res + 1;
}

Compilation message

jumps.cpp: In function 'int lca(int, int)':
jumps.cpp:50:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   50 |   if (h[v] - h[u] >> i & 1)
      |       ~~~~~^~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 165 ms 26536 KB Output is correct
4 Correct 1088 ms 33160 KB Output is correct
5 Correct 1004 ms 16956 KB Output is correct
6 Correct 992 ms 33164 KB Output is correct
7 Correct 879 ms 22784 KB Output is correct
8 Correct 1155 ms 33160 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Incorrect 2 ms 420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Incorrect 2 ms 420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 38 ms 26812 KB Output is correct
6 Correct 43 ms 33168 KB Output is correct
7 Correct 20 ms 17188 KB Output is correct
8 Incorrect 42 ms 33152 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Incorrect 275 ms 15576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Incorrect 275 ms 15576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 165 ms 26536 KB Output is correct
4 Correct 1088 ms 33160 KB Output is correct
5 Correct 1004 ms 16956 KB Output is correct
6 Correct 992 ms 33164 KB Output is correct
7 Correct 879 ms 22784 KB Output is correct
8 Correct 1155 ms 33160 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Incorrect 2 ms 420 KB Output isn't correct
14 Halted 0 ms 0 KB -