oj.uz

Submission #533878

# Submission time Handle Problem Language Result Execution time Memory
533878 2022-03-07T14:24:45 Z hollwo_pelw Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1186 ms 33676 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] && big_jmp[i][u] < c) {
			res += 1 << i;
			u = big_jmp[i][u];
		}

	if (u < c && h[big_jmp[0][u]] >= h[v]) {
		res ++;
		u = big_jmp[0][u];
	}

	if (c <= u && u <= d)
		return res;

	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 1 ms 456 KB Output is correct
3 Correct 152 ms 26580 KB Output is correct
4 Correct 1130 ms 33160 KB Output is correct
5 Correct 883 ms 16936 KB Output is correct
6 Correct 1169 ms 33072 KB Output is correct
7 Correct 814 ms 22820 KB Output is correct
8 Correct 1186 ms 33060 KB Output is correct

Subtask #2
0 / 8.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 0 ms 456 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Incorrect 2 ms 456 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 0 ms 456 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Incorrect 2 ms 456 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 0 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 37 ms 26780 KB Output is correct
6 Correct 47 ms 33172 KB Output is correct
7 Correct 21 ms 17200 KB Output is correct
8 Correct 41 ms 33036 KB Output is correct
9 Correct 6 ms 5448 KB Output is correct
10 Correct 41 ms 33080 KB Output is correct
11 Correct 35 ms 33164 KB Output is correct
12 Incorrect 38 ms 33328 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
23.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 Correct 270 ms 15448 KB Output is correct
5 Correct 970 ms 33188 KB Output is correct
6 Correct 647 ms 5828 KB Output is correct
7 Correct 874 ms 33152 KB Output is correct
8 Correct 535 ms 11704 KB Output is correct
9 Correct 859 ms 33060 KB Output is correct
10 Correct 1150 ms 33072 KB Output is correct
11 Correct 1018 ms 33676 KB Output is correct
12 Correct 1020 ms 33072 KB Output is correct
13 Correct 632 ms 33072 KB Output is correct
14 Correct 1010 ms 33440 KB Output is correct
15 Correct 930 ms 33180 KB Output is correct
16 Correct 788 ms 33192 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 2 ms 456 KB Output is correct
20 Correct 3 ms 456 KB Output is correct
21 Correct 3 ms 456 KB Output is correct
22 Correct 3 ms 456 KB Output is correct
23 Correct 2 ms 456 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 1 ms 456 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 13 ms 840 KB Output is correct
28 Correct 19 ms 712 KB Output is correct
29 Correct 22 ms 840 KB Output is correct
30 Correct 21 ms 840 KB Output is correct
31 Correct 20 ms 840 KB Output is correct
32 Correct 1 ms 456 KB Output is correct
33 Correct 34 ms 19408 KB Output is correct
34 Correct 41 ms 33160 KB Output is correct
35 Correct 37 ms 33124 KB Output is correct
36 Correct 44 ms 33072 KB Output is correct
37 Correct 35 ms 33464 KB Output is correct
38 Correct 37 ms 33288 KB Output is correct

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 Correct 270 ms 15448 KB Output is correct
5 Correct 970 ms 33188 KB Output is correct
6 Correct 647 ms 5828 KB Output is correct
7 Correct 874 ms 33152 KB Output is correct
8 Correct 535 ms 11704 KB Output is correct
9 Correct 859 ms 33060 KB Output is correct
10 Correct 1150 ms 33072 KB Output is correct
11 Correct 1018 ms 33676 KB Output is correct
12 Correct 1020 ms 33072 KB Output is correct
13 Correct 632 ms 33072 KB Output is correct
14 Correct 1010 ms 33440 KB Output is correct
15 Correct 930 ms 33180 KB Output is correct
16 Correct 788 ms 33192 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 2 ms 456 KB Output is correct
20 Correct 3 ms 456 KB Output is correct
21 Correct 3 ms 456 KB Output is correct
22 Correct 3 ms 456 KB Output is correct
23 Correct 2 ms 456 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 1 ms 456 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 13 ms 840 KB Output is correct
28 Correct 19 ms 712 KB Output is correct
29 Correct 22 ms 840 KB Output is correct
30 Correct 21 ms 840 KB Output is correct
31 Correct 20 ms 840 KB Output is correct
32 Correct 1 ms 456 KB Output is correct
33 Correct 34 ms 19408 KB Output is correct
34 Correct 41 ms 33160 KB Output is correct
35 Correct 37 ms 33124 KB Output is correct
36 Correct 44 ms 33072 KB Output is correct
37 Correct 35 ms 33464 KB Output is correct
38 Correct 37 ms 33288 KB Output is correct
39 Correct 1 ms 456 KB Output is correct
40 Correct 1 ms 456 KB Output is correct
41 Correct 1 ms 456 KB Output is correct
42 Correct 276 ms 15500 KB Output is correct
43 Correct 961 ms 33056 KB Output is correct
44 Correct 633 ms 5828 KB Output is correct
45 Correct 855 ms 33164 KB Output is correct
46 Correct 571 ms 11696 KB Output is correct
47 Correct 1018 ms 33100 KB Output is correct
48 Correct 1000 ms 33160 KB Output is correct
49 Correct 1141 ms 33676 KB Output is correct
50 Correct 1116 ms 33060 KB Output is correct
51 Correct 968 ms 33076 KB Output is correct
52 Correct 1042 ms 33444 KB Output is correct
53 Correct 812 ms 33200 KB Output is correct
54 Correct 853 ms 33164 KB Output is correct
55 Correct 1 ms 456 KB Output is correct
56 Incorrect 103 ms 33120 KB Output isn't correct
57 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 1 ms 456 KB Output is correct
3 Correct 152 ms 26580 KB Output is correct
4 Correct 1130 ms 33160 KB Output is correct
5 Correct 883 ms 16936 KB Output is correct
6 Correct 1169 ms 33072 KB Output is correct
7 Correct 814 ms 22820 KB Output is correct
8 Correct 1186 ms 33060 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Incorrect 2 ms 456 KB Output isn't correct
14 Halted 0 ms 0 KB -