oj.uz

Submission #937355

# Submission time Handle Problem Language Result Execution time Memory
937355 2024-03-04T00:30:48 Z gustavo_d Birthday gift (IZhO18_treearray) C++17
100 / 100
 1925 ms 58244 KB 
// https://oj.uz/problem/view/IZhO18_treearray > p203
#include <bits/stdc++.h>
using namespace std;

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

vector<int> adj[MAXN];
int a[MAXN];

int nivel[MAXN];
bool vis[MAXN];
int f[MAXLOG+1][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);
			}
		}
	}
}

int LCA(int x, int y) {
	if (nivel[x] < nivel[y]) swap(x, y); // x sobe
	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][x] != -1 and nivel[f[b][x]] >= nivel[y]) {
			x = f[b][x];
		}
	}
	if (x == y) return x;

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

	return f[0][x];
}

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);
	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]];
			}
		}
	}

	set<pair<int,int>> lcas; // {lca(i, i+1), i}
	set<pair<int,int>> itself;
	for (int i=0; i<m; i++) {
		cin >> a[i];
		a[i]--;
		if (i >= 1) {
			lcas.insert({LCA(a[i-1], a[i]), i-1});
		}
		itself.insert({a[i], i});
	}

	for (int q=0; q<qs; q++) {
		int type; cin >> type;
		if (type == 1) {
			int i, v; cin >> i >> v; // a[i] = v
			i--; v--;

			if (i != m-1) lcas.erase({LCA(a[i], a[i+1]), i});
			if (i != 0) lcas.erase({LCA(a[i-1], a[i]), i-1});
			itself.erase({a[i], i});
			a[i] = v;
			itself.insert({a[i], i});
			if (i != m-1) lcas.insert({LCA(a[i], a[i+1]), i});
			if (i != 0) lcas.insert({LCA(a[i-1], a[i]), i-1});
		} else {
			int l, r, v; cin >> l >> r >> v; // LCA = v entre l e r
			l--; r--; v--;
			auto it = itself.lower_bound({v, l});
			if (it == itself.end() or ((it->first) != v) or ((it->second) > r)) {}
			else {
				cout << (it->second)+1 << ' ' << (it->second) + 1 << '\n';
				continue;
			}
			it = lcas.lower_bound({v, l});
			if (it == lcas.end()) {
				cout << "-1 -1\n";
			} else {
				if ((it->first) != v) cout << "-1 -1\n";
				else if ((it->second) >= r) cout << "-1 -1\n"; // pega r+1 ou maior
				else cout << (it->second)+1 << ' ' << (it->second) + 2 << '\n';
			}
		}
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB n=5
2 Correct 4 ms 23388 KB n=100
3 Correct 4 ms 23132 KB n=100
4 Correct 5 ms 23132 KB n=100
5 Correct 4 ms 23132 KB n=100
6 Correct 3 ms 23132 KB n=100
7 Correct 4 ms 23128 KB n=100
8 Correct 4 ms 23132 KB n=100
9 Correct 4 ms 23132 KB n=100
10 Correct 3 ms 23132 KB n=100
11 Correct 4 ms 23172 KB n=100
12 Correct 4 ms 23152 KB n=100
13 Correct 4 ms 23132 KB n=100
14 Correct 4 ms 23132 KB n=100
15 Correct 4 ms 23132 KB n=100
16 Correct 4 ms 23132 KB n=100
17 Correct 4 ms 23132 KB n=100
18 Correct 4 ms 23132 KB n=100
19 Correct 4 ms 23132 KB n=100
20 Correct 3 ms 23132 KB n=100
21 Correct 4 ms 23132 KB n=100
22 Correct 4 ms 23132 KB n=100
23 Correct 4 ms 23144 KB n=100
24 Correct 4 ms 23348 KB n=100
25 Correct 3 ms 23132 KB n=100
26 Correct 4 ms 23132 KB n=12
27 Correct 4 ms 23132 KB n=100
28 Correct 4 ms 23132 KB n=500
29 Correct 5 ms 23384 KB n=500
30 Correct 4 ms 23132 KB n=500
31 Correct 4 ms 23132 KB n=500
32 Correct 4 ms 23132 KB n=500
33 Correct 4 ms 23128 KB n=500
34 Correct 4 ms 23132 KB n=500
35 Correct 4 ms 23132 KB n=500
36 Correct 4 ms 23132 KB n=500
37 Correct 4 ms 23216 KB n=500
38 Correct 4 ms 23132 KB n=500
39 Correct 4 ms 23132 KB n=500
40 Correct 4 ms 23132 KB n=500
41 Correct 5 ms 23244 KB n=500
42 Correct 4 ms 23132 KB n=500
43 Correct 4 ms 23132 KB n=500
44 Correct 4 ms 23132 KB n=500
45 Correct 4 ms 23156 KB n=500
46 Correct 4 ms 23132 KB n=500
47 Correct 4 ms 23132 KB n=500
48 Correct 4 ms 23132 KB n=500
49 Correct 5 ms 23132 KB n=500
50 Correct 4 ms 23132 KB n=500
51 Correct 5 ms 23132 KB n=500
52 Correct 4 ms 23128 KB n=500
53 Correct 4 ms 23132 KB n=500
54 Correct 4 ms 23132 KB n=500
55 Correct 4 ms 23132 KB n=278
56 Correct 4 ms 23132 KB n=500
57 Correct 4 ms 23128 KB n=500
58 Correct 4 ms 23132 KB n=500
59 Correct 6 ms 23388 KB n=2000
60 Correct 7 ms 23388 KB n=2000
61 Correct 7 ms 23388 KB n=2000
62 Correct 7 ms 23384 KB n=2000
63 Correct 6 ms 23388 KB n=2000
64 Correct 7 ms 23388 KB n=2000
65 Correct 7 ms 23612 KB n=2000
66 Correct 7 ms 23388 KB n=2000
67 Correct 6 ms 23388 KB n=2000
68 Correct 7 ms 23428 KB n=2000
69 Correct 6 ms 23388 KB n=2000
70 Correct 5 ms 23388 KB n=2000
71 Correct 5 ms 23388 KB n=2000
72 Correct 6 ms 23388 KB n=2000
73 Correct 5 ms 23388 KB n=2000
74 Correct 6 ms 23388 KB n=1844
75 Correct 5 ms 23388 KB n=2000
76 Correct 6 ms 23388 KB n=2000
77 Correct 6 ms 23416 KB n=2000
78 Correct 7 ms 23388 KB n=2000
79 Correct 6 ms 23388 KB n=2000
80 Correct 7 ms 23388 KB n=2000
81 Correct 7 ms 23388 KB n=2000
82 Correct 6 ms 23388 KB n=2000
83 Correct 7 ms 23388 KB n=2000
84 Correct 6 ms 23388 KB n=2000
85 Correct 7 ms 23388 KB n=2000
86 Correct 7 ms 23388 KB n=2000
87 Correct 6 ms 23388 KB n=2000
88 Correct 6 ms 23388 KB n=2000
89 Correct 7 ms 23388 KB n=2000
90 Correct 7 ms 23388 KB n=2000
91 Correct 5 ms 23388 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB n=5
2 Correct 4 ms 23388 KB n=100
3 Correct 4 ms 23132 KB n=100
4 Correct 5 ms 23132 KB n=100
5 Correct 4 ms 23132 KB n=100
6 Correct 3 ms 23132 KB n=100
7 Correct 4 ms 23128 KB n=100
8 Correct 4 ms 23132 KB n=100
9 Correct 4 ms 23132 KB n=100
10 Correct 3 ms 23132 KB n=100
11 Correct 4 ms 23172 KB n=100
12 Correct 4 ms 23152 KB n=100
13 Correct 4 ms 23132 KB n=100
14 Correct 4 ms 23132 KB n=100
15 Correct 4 ms 23132 KB n=100
16 Correct 4 ms 23132 KB n=100
17 Correct 4 ms 23132 KB n=100
18 Correct 4 ms 23132 KB n=100
19 Correct 4 ms 23132 KB n=100
20 Correct 3 ms 23132 KB n=100
21 Correct 4 ms 23132 KB n=100
22 Correct 4 ms 23132 KB n=100
23 Correct 4 ms 23144 KB n=100
24 Correct 4 ms 23348 KB n=100
25 Correct 3 ms 23132 KB n=100
26 Correct 4 ms 23132 KB n=12
27 Correct 4 ms 23132 KB n=100
28 Correct 4 ms 23132 KB n=500
29 Correct 5 ms 23384 KB n=500
30 Correct 4 ms 23132 KB n=500
31 Correct 4 ms 23132 KB n=500
32 Correct 4 ms 23132 KB n=500
33 Correct 4 ms 23128 KB n=500
34 Correct 4 ms 23132 KB n=500
35 Correct 4 ms 23132 KB n=500
36 Correct 4 ms 23132 KB n=500
37 Correct 4 ms 23216 KB n=500
38 Correct 4 ms 23132 KB n=500
39 Correct 4 ms 23132 KB n=500
40 Correct 4 ms 23132 KB n=500
41 Correct 5 ms 23244 KB n=500
42 Correct 4 ms 23132 KB n=500
43 Correct 4 ms 23132 KB n=500
44 Correct 4 ms 23132 KB n=500
45 Correct 4 ms 23156 KB n=500
46 Correct 4 ms 23132 KB n=500
47 Correct 4 ms 23132 KB n=500
48 Correct 4 ms 23132 KB n=500
49 Correct 5 ms 23132 KB n=500
50 Correct 4 ms 23132 KB n=500
51 Correct 5 ms 23132 KB n=500
52 Correct 4 ms 23128 KB n=500
53 Correct 4 ms 23132 KB n=500
54 Correct 4 ms 23132 KB n=500
55 Correct 4 ms 23132 KB n=278
56 Correct 4 ms 23132 KB n=500
57 Correct 4 ms 23128 KB n=500
58 Correct 4 ms 23132 KB n=500
59 Correct 6 ms 23388 KB n=2000
60 Correct 7 ms 23388 KB n=2000
61 Correct 7 ms 23388 KB n=2000
62 Correct 7 ms 23384 KB n=2000
63 Correct 6 ms 23388 KB n=2000
64 Correct 7 ms 23388 KB n=2000
65 Correct 7 ms 23612 KB n=2000
66 Correct 7 ms 23388 KB n=2000
67 Correct 6 ms 23388 KB n=2000
68 Correct 7 ms 23428 KB n=2000
69 Correct 6 ms 23388 KB n=2000
70 Correct 5 ms 23388 KB n=2000
71 Correct 5 ms 23388 KB n=2000
72 Correct 6 ms 23388 KB n=2000
73 Correct 5 ms 23388 KB n=2000
74 Correct 6 ms 23388 KB n=1844
75 Correct 5 ms 23388 KB n=2000
76 Correct 6 ms 23388 KB n=2000
77 Correct 6 ms 23416 KB n=2000
78 Correct 7 ms 23388 KB n=2000
79 Correct 6 ms 23388 KB n=2000
80 Correct 7 ms 23388 KB n=2000
81 Correct 7 ms 23388 KB n=2000
82 Correct 6 ms 23388 KB n=2000
83 Correct 7 ms 23388 KB n=2000
84 Correct 6 ms 23388 KB n=2000
85 Correct 7 ms 23388 KB n=2000
86 Correct 7 ms 23388 KB n=2000
87 Correct 6 ms 23388 KB n=2000
88 Correct 6 ms 23388 KB n=2000
89 Correct 7 ms 23388 KB n=2000
90 Correct 7 ms 23388 KB n=2000
91 Correct 5 ms 23388 KB n=2000
92 Correct 838 ms 56728 KB n=200000
93 Correct 1772 ms 57264 KB n=200000
94 Correct 1778 ms 57276 KB n=200000
95 Correct 777 ms 56676 KB n=200000
96 Correct 856 ms 57044 KB n=200000
97 Correct 1791 ms 57312 KB n=200000
98 Correct 796 ms 56736 KB n=200000
99 Correct 1098 ms 57028 KB n=200000
100 Correct 804 ms 56984 KB n=200000
101 Correct 1696 ms 57132 KB n=200000
102 Correct 472 ms 57896 KB n=200000
103 Correct 501 ms 58196 KB n=200000
104 Correct 496 ms 57728 KB n=200000
105 Correct 537 ms 58180 KB n=200000
106 Correct 422 ms 58192 KB n=200000
107 Correct 476 ms 58244 KB n=200000
108 Correct 1117 ms 56912 KB n=200000
109 Correct 1062 ms 56940 KB n=200000
110 Correct 1054 ms 56792 KB n=200000
111 Correct 770 ms 56104 KB n=200000
112 Correct 1791 ms 57288 KB n=200000
113 Correct 1734 ms 57116 KB n=200000
114 Correct 780 ms 56004 KB n=200000
115 Correct 1768 ms 57068 KB n=200000
116 Correct 828 ms 57116 KB n=200000
117 Correct 1925 ms 57032 KB n=200000
118 Correct 1729 ms 57160 KB n=200000
119 Correct 898 ms 57284 KB n=200000
120 Correct 1873 ms 55736 KB n=200000
121 Correct 1762 ms 55884 KB n=200000
122 Correct 1608 ms 56400 KB n=200000
123 Correct 517 ms 57912 KB n=200000
124 Correct 293 ms 34640 KB n=25264