oj.uz

Submission #942595

# Submission time Handle Problem Language Result Execution time Memory
942595 2024-03-11T00:57:37 Z gustavo_d Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 33968 KB 
// https://oj.uz/problem/view/IZhO18_treearray > p203
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("unroll-loops,O3")

const int MAXN = 2e5;
const int MAXLOG = 20;

vector<int> adj[MAXN];
int f[MAXLOG+1][MAXN];
int nivel[MAXN];
bool vis[MAXN];

void BFS(int src) {
	vis[src] = true;
	nivel[src] = 0;
	f[0][src] = -1;
	queue<int> visit; visit.push(src);
	while (!visit.empty()) {
		int v = visit.front();
		visit.pop();
		for (int viz : adj[v]) {
			if (!vis[viz]) {
				vis[viz] = true;
				nivel[viz] = nivel[v] + 1;
				f[0][viz] = v;
				visit.push(viz);
			}
		}
	}
}

// DP de memorização se der TLE
int LCA(int u, int v) {
	if (u == -1) return v;
	if (v == -1) return u;
	if (nivel[u] < nivel[v]) swap(u, v);
	// sobe o u
	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][u] != -1 and nivel[f[b][u]] >= nivel[v]) {
			u = f[b][u];
		}
	}

	if (u == v) return u;
	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][u] != -1 and f[b][v] != -1 and
			f[b][u] != f[b][v]) {
			u = f[b][u];
			v = f[b][v];
		}
	}
	return f[0][u];
}

struct Node {
	int lca;

	Node(int _lca=-1): lca(_lca) {}

	Node operator+(Node right) {
		Node left = *this;
		return LCA(
			left.lca,
			right.lca
		);
	}
};

struct SEG {
	vector<Node> seg;
	int n, actual_lca;
	vector<pair<int, pair<int,int>>> possible;

	SEG(vector<int> &a) {
		n = 1;
		while (n < (int)a.size()) n <<= 1;

		seg = vector<Node> (2 * n);
		for (int i=0; i<(int)a.size(); i++) {
			seg[i+n].lca = a[i];
		}
		for (int i=n-1; i>=0; i--) {
			seg[i] = seg[2*i] + seg[2*i+1];
		}
	}

	void update(int v, int l, int r, int i, int val) {
		if (l == r) {
			seg[v] = val;
			return;
		}

		int m = (l + r) / 2;
		if (i <= m) update(2*v, l, m, i, val);
		else update(2*v+1, m+1, r, i, val);
		seg[v] = seg[2*v] + seg[2*v+1];
	}

	pair<int, pair<int,int>> find_start_node(int l, int r, int v) {
		possible.clear();
		find_nodes(1, 0, n-1, l, r);

		int act = -1;
		for (pair<int, pair<int,int>> node : possible) {
			actual_lca = act;
			act = LCA(act, seg[node.first].lca);
			if (nivel[act] <= nivel[v]) {
				// é um mais alto
				return node;
			}
		}
		return {-1, {-1,-1}};
	}

	void find_nodes(int v, int l, int r, int a, int b) {
		// contido
		if (a <= l and r <= b) {
			possible.push_back({v, {l, r}});
			return;
		}

		// fora
		if (r < a or l > b) return;

		// pacialmente contido
		int m = (l + r) / 2;
		find_nodes(2*v, l, m, a, b);
		find_nodes(2*v+1, m+1, r, a, b);
	}

	int busca_bin(int v, int l, int r, int val) { // primeira posição com lca = v
		if (l == r) {
			if (LCA(actual_lca, seg[v].lca) == val) return l;
			else return -1;
		}

		int m = (l + r) / 2;
		if (nivel[LCA(actual_lca, seg[2*v].lca)] <= nivel[val]) {
			return busca_bin(2*v, l, m, val);
		} else {
			actual_lca = LCA(actual_lca, seg[2*v].lca); // considera range da esquerda já
			return busca_bin(2*v+1, m+1, r, val);
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n, m, qs; cin >> n >> m >> qs;
	for (int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// LCA
	BFS(0);
	// binary lifting
	for (int b=1; b<=MAXLOG; b++) {
		for (int i=0; i<n; i++) {
			if (f[b-1][i] == -1) f[b][i] = -1;
			else {
				f[b][i] = f[b-1][f[b-1][i]];
			}
		}
	}

	vector<int> a(m);
	for (int i=0; i<m; i++) {
		cin >> a[i];
		a[i]--;
	}
	SEG seg = SEG(a);

	for (int q=0; q<qs; q++) {
		int type; cin >> type;
		if (type == 1) {
			int pos, v; cin >> pos >> v;
			// update a[pos] = v;
			pos--; v--;
			seg.update(1, 0, seg.n-1, pos, v);
		} else if (type == 2) {
			int l, r, v; cin >> l >> r >> v;
			l--; r--; v--;
			// -1 -1 ou o x, y com LCA do range = v
			pair<int, int> ans = {-1,-1};
			// cout << "query\n";
			for (int start=l; start<=r and ans == make_pair(-1,-1); start++) {
				pair<int, pair<int,int>> start_node = seg.find_start_node(start, r, v);
				if (start_node.first == -1) continue;
				// cout << start << ' ' << start_node.first << endl;

				ans.second = seg.busca_bin(
					start_node.first,
					start_node.second.first,
					start_node.second.second,
					v
				);
				// cout << ans.second << endl;
				if (ans.second != -1) {
					ans.first = start;
				}
			}
			if (ans == make_pair(-1,-1)) ans = {-2, -2};
			cout << ans.first+1 << ' ' << ans.second+1 << '\n';
		}
	}

	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22364 KB n=5
2 Correct 4 ms 22360 KB n=100
3 Correct 5 ms 22364 KB n=100
4 Correct 4 ms 22360 KB n=100
5 Correct 4 ms 22360 KB n=100
6 Correct 4 ms 22364 KB n=100
7 Correct 4 ms 22364 KB n=100
8 Correct 5 ms 22364 KB n=100
9 Correct 5 ms 22364 KB n=100
10 Correct 4 ms 22364 KB n=100
11 Correct 4 ms 22364 KB n=100
12 Correct 4 ms 22364 KB n=100
13 Correct 4 ms 22364 KB n=100
14 Correct 4 ms 22364 KB n=100
15 Correct 4 ms 22408 KB n=100
16 Correct 4 ms 22364 KB n=100
17 Correct 4 ms 22364 KB n=100
18 Correct 4 ms 22360 KB n=100
19 Correct 3 ms 22364 KB n=100
20 Correct 4 ms 22364 KB n=100
21 Correct 4 ms 22360 KB n=100
22 Correct 4 ms 22364 KB n=100
23 Correct 4 ms 22364 KB n=100
24 Correct 4 ms 22364 KB n=100
25 Correct 4 ms 22360 KB n=100
26 Correct 4 ms 22364 KB n=12
27 Correct 5 ms 22364 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22364 KB n=5
2 Correct 4 ms 22360 KB n=100
3 Correct 5 ms 22364 KB n=100
4 Correct 4 ms 22360 KB n=100
5 Correct 4 ms 22360 KB n=100
6 Correct 4 ms 22364 KB n=100
7 Correct 4 ms 22364 KB n=100
8 Correct 5 ms 22364 KB n=100
9 Correct 5 ms 22364 KB n=100
10 Correct 4 ms 22364 KB n=100
11 Correct 4 ms 22364 KB n=100
12 Correct 4 ms 22364 KB n=100
13 Correct 4 ms 22364 KB n=100
14 Correct 4 ms 22364 KB n=100
15 Correct 4 ms 22408 KB n=100
16 Correct 4 ms 22364 KB n=100
17 Correct 4 ms 22364 KB n=100
18 Correct 4 ms 22360 KB n=100
19 Correct 3 ms 22364 KB n=100
20 Correct 4 ms 22364 KB n=100
21 Correct 4 ms 22360 KB n=100
22 Correct 4 ms 22364 KB n=100
23 Correct 4 ms 22364 KB n=100
24 Correct 4 ms 22364 KB n=100
25 Correct 4 ms 22360 KB n=100
26 Correct 4 ms 22364 KB n=12
27 Correct 5 ms 22364 KB n=100
28 Correct 4 ms 22364 KB n=500
29 Correct 9 ms 22360 KB n=500
30 Correct 9 ms 22364 KB n=500
31 Correct 9 ms 22364 KB n=500
32 Correct 4 ms 22364 KB n=500
33 Correct 8 ms 22364 KB n=500
34 Correct 4 ms 22364 KB n=500
35 Correct 9 ms 22396 KB n=500
36 Correct 27 ms 22360 KB n=500
37 Correct 28 ms 22432 KB n=500
38 Correct 27 ms 22432 KB n=500
39 Correct 18 ms 22360 KB n=500
40 Correct 17 ms 22440 KB n=500
41 Correct 17 ms 22360 KB n=500
42 Correct 16 ms 22364 KB n=500
43 Correct 16 ms 22360 KB n=500
44 Correct 16 ms 22360 KB n=500
45 Correct 4 ms 22364 KB n=500
46 Correct 9 ms 22364 KB n=500
47 Correct 8 ms 22360 KB n=500
48 Correct 4 ms 22364 KB n=500
49 Correct 8 ms 22364 KB n=500
50 Correct 7 ms 22432 KB n=500
51 Correct 10 ms 22364 KB n=500
52 Correct 12 ms 22364 KB n=500
53 Correct 11 ms 22364 KB n=500
54 Correct 12 ms 22620 KB n=500
55 Correct 5 ms 22364 KB n=278
56 Correct 36 ms 22364 KB n=500
57 Correct 36 ms 22364 KB n=500
58 Correct 17 ms 22364 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22364 KB n=5
2 Correct 4 ms 22360 KB n=100
3 Correct 5 ms 22364 KB n=100
4 Correct 4 ms 22360 KB n=100
5 Correct 4 ms 22360 KB n=100
6 Correct 4 ms 22364 KB n=100
7 Correct 4 ms 22364 KB n=100
8 Correct 5 ms 22364 KB n=100
9 Correct 5 ms 22364 KB n=100
10 Correct 4 ms 22364 KB n=100
11 Correct 4 ms 22364 KB n=100
12 Correct 4 ms 22364 KB n=100
13 Correct 4 ms 22364 KB n=100
14 Correct 4 ms 22364 KB n=100
15 Correct 4 ms 22408 KB n=100
16 Correct 4 ms 22364 KB n=100
17 Correct 4 ms 22364 KB n=100
18 Correct 4 ms 22360 KB n=100
19 Correct 3 ms 22364 KB n=100
20 Correct 4 ms 22364 KB n=100
21 Correct 4 ms 22360 KB n=100
22 Correct 4 ms 22364 KB n=100
23 Correct 4 ms 22364 KB n=100
24 Correct 4 ms 22364 KB n=100
25 Correct 4 ms 22360 KB n=100
26 Correct 4 ms 22364 KB n=12
27 Correct 5 ms 22364 KB n=100
28 Correct 4 ms 22364 KB n=500
29 Correct 9 ms 22360 KB n=500
30 Correct 9 ms 22364 KB n=500
31 Correct 9 ms 22364 KB n=500
32 Correct 4 ms 22364 KB n=500
33 Correct 8 ms 22364 KB n=500
34 Correct 4 ms 22364 KB n=500
35 Correct 9 ms 22396 KB n=500
36 Correct 27 ms 22360 KB n=500
37 Correct 28 ms 22432 KB n=500
38 Correct 27 ms 22432 KB n=500
39 Correct 18 ms 22360 KB n=500
40 Correct 17 ms 22440 KB n=500
41 Correct 17 ms 22360 KB n=500
42 Correct 16 ms 22364 KB n=500
43 Correct 16 ms 22360 KB n=500
44 Correct 16 ms 22360 KB n=500
45 Correct 4 ms 22364 KB n=500
46 Correct 9 ms 22364 KB n=500
47 Correct 8 ms 22360 KB n=500
48 Correct 4 ms 22364 KB n=500
49 Correct 8 ms 22364 KB n=500
50 Correct 7 ms 22432 KB n=500
51 Correct 10 ms 22364 KB n=500
52 Correct 12 ms 22364 KB n=500
53 Correct 11 ms 22364 KB n=500
54 Correct 12 ms 22620 KB n=500
55 Correct 5 ms 22364 KB n=278
56 Correct 36 ms 22364 KB n=500
57 Correct 36 ms 22364 KB n=500
58 Correct 17 ms 22364 KB n=500
59 Correct 6 ms 22364 KB n=2000
60 Correct 110 ms 22364 KB n=2000
61 Correct 99 ms 22492 KB n=2000
62 Correct 90 ms 22476 KB n=2000
63 Correct 6 ms 22364 KB n=2000
64 Correct 94 ms 22364 KB n=2000
65 Correct 6 ms 22364 KB n=2000
66 Correct 120 ms 22616 KB n=2000
67 Correct 9 ms 22616 KB n=2000
68 Correct 100 ms 22364 KB n=2000
69 Correct 477 ms 22612 KB n=2000
70 Correct 456 ms 22360 KB n=2000
71 Correct 466 ms 22732 KB n=2000
72 Correct 246 ms 22724 KB n=2000
73 Correct 257 ms 22480 KB n=2000
74 Correct 5 ms 22364 KB n=1844
75 Correct 252 ms 22364 KB n=2000
76 Correct 285 ms 22608 KB n=2000
77 Correct 249 ms 22476 KB n=2000
78 Correct 274 ms 22520 KB n=2000
79 Correct 5 ms 22360 KB n=2000
80 Correct 91 ms 22360 KB n=2000
81 Correct 99 ms 22476 KB n=2000
82 Correct 5 ms 22360 KB n=2000
83 Correct 105 ms 22472 KB n=2000
84 Correct 79 ms 22364 KB n=2000
85 Correct 139 ms 22360 KB n=2000
86 Correct 141 ms 22476 KB n=2000
87 Correct 82 ms 22616 KB n=2000
88 Correct 790 ms 22476 KB n=2000
89 Correct 803 ms 22608 KB n=2000
90 Correct 146 ms 22360 KB n=2000
91 Correct 324 ms 22616 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22364 KB n=5
2 Correct 4 ms 22360 KB n=100
3 Correct 5 ms 22364 KB n=100
4 Correct 4 ms 22360 KB n=100
5 Correct 4 ms 22360 KB n=100
6 Correct 4 ms 22364 KB n=100
7 Correct 4 ms 22364 KB n=100
8 Correct 5 ms 22364 KB n=100
9 Correct 5 ms 22364 KB n=100
10 Correct 4 ms 22364 KB n=100
11 Correct 4 ms 22364 KB n=100
12 Correct 4 ms 22364 KB n=100
13 Correct 4 ms 22364 KB n=100
14 Correct 4 ms 22364 KB n=100
15 Correct 4 ms 22408 KB n=100
16 Correct 4 ms 22364 KB n=100
17 Correct 4 ms 22364 KB n=100
18 Correct 4 ms 22360 KB n=100
19 Correct 3 ms 22364 KB n=100
20 Correct 4 ms 22364 KB n=100
21 Correct 4 ms 22360 KB n=100
22 Correct 4 ms 22364 KB n=100
23 Correct 4 ms 22364 KB n=100
24 Correct 4 ms 22364 KB n=100
25 Correct 4 ms 22360 KB n=100
26 Correct 4 ms 22364 KB n=12
27 Correct 5 ms 22364 KB n=100
28 Correct 4 ms 22364 KB n=500
29 Correct 9 ms 22360 KB n=500
30 Correct 9 ms 22364 KB n=500
31 Correct 9 ms 22364 KB n=500
32 Correct 4 ms 22364 KB n=500
33 Correct 8 ms 22364 KB n=500
34 Correct 4 ms 22364 KB n=500
35 Correct 9 ms 22396 KB n=500
36 Correct 27 ms 22360 KB n=500
37 Correct 28 ms 22432 KB n=500
38 Correct 27 ms 22432 KB n=500
39 Correct 18 ms 22360 KB n=500
40 Correct 17 ms 22440 KB n=500
41 Correct 17 ms 22360 KB n=500
42 Correct 16 ms 22364 KB n=500
43 Correct 16 ms 22360 KB n=500
44 Correct 16 ms 22360 KB n=500
45 Correct 4 ms 22364 KB n=500
46 Correct 9 ms 22364 KB n=500
47 Correct 8 ms 22360 KB n=500
48 Correct 4 ms 22364 KB n=500
49 Correct 8 ms 22364 KB n=500
50 Correct 7 ms 22432 KB n=500
51 Correct 10 ms 22364 KB n=500
52 Correct 12 ms 22364 KB n=500
53 Correct 11 ms 22364 KB n=500
54 Correct 12 ms 22620 KB n=500
55 Correct 5 ms 22364 KB n=278
56 Correct 36 ms 22364 KB n=500
57 Correct 36 ms 22364 KB n=500
58 Correct 17 ms 22364 KB n=500
59 Correct 6 ms 22364 KB n=2000
60 Correct 110 ms 22364 KB n=2000
61 Correct 99 ms 22492 KB n=2000
62 Correct 90 ms 22476 KB n=2000
63 Correct 6 ms 22364 KB n=2000
64 Correct 94 ms 22364 KB n=2000
65 Correct 6 ms 22364 KB n=2000
66 Correct 120 ms 22616 KB n=2000
67 Correct 9 ms 22616 KB n=2000
68 Correct 100 ms 22364 KB n=2000
69 Correct 477 ms 22612 KB n=2000
70 Correct 456 ms 22360 KB n=2000
71 Correct 466 ms 22732 KB n=2000
72 Correct 246 ms 22724 KB n=2000
73 Correct 257 ms 22480 KB n=2000
74 Correct 5 ms 22364 KB n=1844
75 Correct 252 ms 22364 KB n=2000
76 Correct 285 ms 22608 KB n=2000
77 Correct 249 ms 22476 KB n=2000
78 Correct 274 ms 22520 KB n=2000
79 Correct 5 ms 22360 KB n=2000
80 Correct 91 ms 22360 KB n=2000
81 Correct 99 ms 22476 KB n=2000
82 Correct 5 ms 22360 KB n=2000
83 Correct 105 ms 22472 KB n=2000
84 Correct 79 ms 22364 KB n=2000
85 Correct 139 ms 22360 KB n=2000
86 Correct 141 ms 22476 KB n=2000
87 Correct 82 ms 22616 KB n=2000
88 Correct 790 ms 22476 KB n=2000
89 Correct 803 ms 22608 KB n=2000
90 Correct 146 ms 22360 KB n=2000
91 Correct 324 ms 22616 KB n=2000
92 Correct 1410 ms 33968 KB n=200000
93 Execution timed out 4041 ms 31568 KB Time limit exceeded
94 Halted 0 ms 0 KB -