oj.uz

Submission #912773

# Submission time Handle Problem Language Result Execution time Memory
912773 2024-01-19T22:02:31 Z OAleksa Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 61776 KB 
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 19;
int up[N][K], a[N], tin[N], tout[N], timer, m;
int n, q, st[4 * N];
vector<int> g[N];
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr)
		st[v] = x;
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			modify(v * 2, tl, mid, p, x);
		else
			modify(v * 2 + 1, mid + 1, tr, p, x);
		st[v] = Lca(st[v * 2], st[v * 2 + 1]);
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return -1;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		int left = get(v * 2, tl, mid, l, r);
		int right = get(v * 2 + 1, mid + 1, tr, l, r);
		assert(left != -1 || right != -1);
		if (left != -1 && right != -1)
			return Lca(left, right);
		else if (left != -1)
			return left;
		else
			return right;
	}
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> m >> q;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= m;i++) {
  		cin >> a[i];
  		modify(1, 1, m, i, a[i]);
  	}
  	while (q--) {
  		int t;
  		cin >> t;
  		if (t == 1) {
  			int pos, v;
  			cin >> pos >> v;
  			modify(1, 1, m, pos, v);
  			a[pos] = v;
  		}
  		else {
  			int tl, tr, v;
  			cin >> tl >> tr >> v;
  			int x = -1, y = -1;
  			for (int i = tl;i <= tr;i++) {
  				int l = tl, r = i, id = i;
  				if (!anc(v, a[i]))
  					continue;
  				while (l <= r) {
  					int mid = (l + r) / 2;
  					int x = get(1, 1, m, mid, i);
  					if (anc(x, v)) {
  						l = mid + 1;
  						id = mid;
  					}
  					else
  						r = mid - 1;
  				}
  				int t = get(1, 1, m, id, i);
  				if (t == v) {
  					x = id, y = i;
  					break;
  				}
  			}
  			cout << x << ' ' << y << '\n';
  		}
  	}
	}
  return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB n=5
2 Correct 2 ms 12952 KB n=100
3 Correct 3 ms 12892 KB n=100
4 Correct 3 ms 12892 KB n=100
5 Correct 3 ms 12892 KB n=100
6 Correct 4 ms 12892 KB n=100
7 Correct 5 ms 12888 KB n=100
8 Correct 4 ms 12888 KB n=100
9 Correct 3 ms 12892 KB n=100
10 Correct 3 ms 12892 KB n=100
11 Correct 3 ms 12892 KB n=100
12 Correct 3 ms 12888 KB n=100
13 Correct 4 ms 12888 KB n=100
14 Correct 3 ms 12892 KB n=100
15 Correct 3 ms 12892 KB n=100
16 Correct 3 ms 12892 KB n=100
17 Correct 3 ms 12892 KB n=100
18 Correct 3 ms 12892 KB n=100
19 Correct 3 ms 12892 KB n=100
20 Correct 3 ms 12892 KB n=100
21 Correct 4 ms 12892 KB n=100
22 Correct 3 ms 12888 KB n=100
23 Correct 4 ms 12892 KB n=100
24 Correct 4 ms 12892 KB n=100
25 Correct 3 ms 12908 KB n=100
26 Correct 3 ms 12892 KB n=12
27 Correct 3 ms 12888 KB n=100
28 Correct 4 ms 12892 KB n=500
29 Correct 18 ms 12896 KB n=500
30 Correct 16 ms 12888 KB n=500
31 Correct 18 ms 12976 KB n=500
32 Correct 3 ms 12892 KB n=500
33 Correct 18 ms 12892 KB n=500
34 Correct 4 ms 12892 KB n=500
35 Correct 16 ms 12888 KB n=500
36 Correct 63 ms 12892 KB n=500
37 Correct 67 ms 12976 KB n=500
38 Correct 64 ms 12888 KB n=500
39 Correct 34 ms 12892 KB n=500
40 Correct 31 ms 12968 KB n=500
41 Correct 32 ms 12984 KB n=500
42 Correct 42 ms 13144 KB n=500
43 Correct 34 ms 12980 KB n=500
44 Correct 31 ms 12892 KB n=500
45 Correct 3 ms 12892 KB n=500
46 Correct 18 ms 12892 KB n=500
47 Correct 14 ms 12888 KB n=500
48 Correct 4 ms 12940 KB n=500
49 Correct 15 ms 12888 KB n=500
50 Correct 4 ms 12888 KB n=500
51 Correct 16 ms 12996 KB n=500
52 Correct 25 ms 12892 KB n=500
53 Correct 12 ms 13144 KB n=500
54 Correct 54 ms 12980 KB n=500
55 Correct 6 ms 12888 KB n=278
56 Correct 128 ms 12976 KB n=500
57 Correct 127 ms 12976 KB n=500
58 Correct 4 ms 12892 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB n=5
2 Correct 2 ms 12952 KB n=100
3 Correct 3 ms 12892 KB n=100
4 Correct 3 ms 12892 KB n=100
5 Correct 3 ms 12892 KB n=100
6 Correct 4 ms 12892 KB n=100
7 Correct 5 ms 12888 KB n=100
8 Correct 4 ms 12888 KB n=100
9 Correct 3 ms 12892 KB n=100
10 Correct 3 ms 12892 KB n=100
11 Correct 3 ms 12892 KB n=100
12 Correct 3 ms 12888 KB n=100
13 Correct 4 ms 12888 KB n=100
14 Correct 3 ms 12892 KB n=100
15 Correct 3 ms 12892 KB n=100
16 Correct 3 ms 12892 KB n=100
17 Correct 3 ms 12892 KB n=100
18 Correct 3 ms 12892 KB n=100
19 Correct 3 ms 12892 KB n=100
20 Correct 3 ms 12892 KB n=100
21 Correct 4 ms 12892 KB n=100
22 Correct 3 ms 12888 KB n=100
23 Correct 4 ms 12892 KB n=100
24 Correct 4 ms 12892 KB n=100
25 Correct 3 ms 12908 KB n=100
26 Correct 3 ms 12892 KB n=12
27 Correct 3 ms 12888 KB n=100
28 Correct 4 ms 12892 KB n=500
29 Correct 18 ms 12896 KB n=500
30 Correct 16 ms 12888 KB n=500
31 Correct 18 ms 12976 KB n=500
32 Correct 3 ms 12892 KB n=500
33 Correct 18 ms 12892 KB n=500
34 Correct 4 ms 12892 KB n=500
35 Correct 16 ms 12888 KB n=500
36 Correct 63 ms 12892 KB n=500
37 Correct 67 ms 12976 KB n=500
38 Correct 64 ms 12888 KB n=500
39 Correct 34 ms 12892 KB n=500
40 Correct 31 ms 12968 KB n=500
41 Correct 32 ms 12984 KB n=500
42 Correct 42 ms 13144 KB n=500
43 Correct 34 ms 12980 KB n=500
44 Correct 31 ms 12892 KB n=500
45 Correct 3 ms 12892 KB n=500
46 Correct 18 ms 12892 KB n=500
47 Correct 14 ms 12888 KB n=500
48 Correct 4 ms 12940 KB n=500
49 Correct 15 ms 12888 KB n=500
50 Correct 4 ms 12888 KB n=500
51 Correct 16 ms 12996 KB n=500
52 Correct 25 ms 12892 KB n=500
53 Correct 12 ms 13144 KB n=500
54 Correct 54 ms 12980 KB n=500
55 Correct 6 ms 12888 KB n=278
56 Correct 128 ms 12976 KB n=500
57 Correct 127 ms 12976 KB n=500
58 Correct 4 ms 12892 KB n=500
59 Correct 5 ms 12892 KB n=2000
60 Correct 342 ms 13148 KB n=2000
61 Correct 320 ms 13112 KB n=2000
62 Correct 212 ms 13084 KB n=2000
63 Correct 6 ms 12888 KB n=2000
64 Correct 291 ms 13096 KB n=2000
65 Correct 5 ms 12892 KB n=2000
66 Correct 377 ms 13116 KB n=2000
67 Correct 8 ms 12972 KB n=2000
68 Correct 301 ms 13104 KB n=2000
69 Correct 1495 ms 13080 KB n=2000
70 Correct 1493 ms 13072 KB n=2000
71 Correct 1535 ms 13152 KB n=2000
72 Correct 702 ms 13076 KB n=2000
73 Correct 703 ms 13140 KB n=2000
74 Correct 5 ms 12892 KB n=1844
75 Correct 745 ms 13324 KB n=2000
76 Correct 766 ms 13136 KB n=2000
77 Correct 757 ms 13060 KB n=2000
78 Correct 821 ms 13064 KB n=2000
79 Correct 5 ms 12888 KB n=2000
80 Correct 287 ms 13128 KB n=2000
81 Correct 267 ms 13140 KB n=2000
82 Correct 7 ms 12888 KB n=2000
83 Correct 280 ms 13116 KB n=2000
84 Correct 7 ms 12892 KB n=2000
85 Correct 210 ms 13280 KB n=2000
86 Correct 151 ms 12892 KB n=2000
87 Correct 8 ms 12888 KB n=2000
88 Correct 3173 ms 13148 KB n=2000
89 Correct 3204 ms 13144 KB n=2000
90 Correct 1255 ms 13148 KB n=2000
91 Correct 12 ms 12888 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB n=5
2 Correct 2 ms 12952 KB n=100
3 Correct 3 ms 12892 KB n=100
4 Correct 3 ms 12892 KB n=100
5 Correct 3 ms 12892 KB n=100
6 Correct 4 ms 12892 KB n=100
7 Correct 5 ms 12888 KB n=100
8 Correct 4 ms 12888 KB n=100
9 Correct 3 ms 12892 KB n=100
10 Correct 3 ms 12892 KB n=100
11 Correct 3 ms 12892 KB n=100
12 Correct 3 ms 12888 KB n=100
13 Correct 4 ms 12888 KB n=100
14 Correct 3 ms 12892 KB n=100
15 Correct 3 ms 12892 KB n=100
16 Correct 3 ms 12892 KB n=100
17 Correct 3 ms 12892 KB n=100
18 Correct 3 ms 12892 KB n=100
19 Correct 3 ms 12892 KB n=100
20 Correct 3 ms 12892 KB n=100
21 Correct 4 ms 12892 KB n=100
22 Correct 3 ms 12888 KB n=100
23 Correct 4 ms 12892 KB n=100
24 Correct 4 ms 12892 KB n=100
25 Correct 3 ms 12908 KB n=100
26 Correct 3 ms 12892 KB n=12
27 Correct 3 ms 12888 KB n=100
28 Correct 4 ms 12892 KB n=500
29 Correct 18 ms 12896 KB n=500
30 Correct 16 ms 12888 KB n=500
31 Correct 18 ms 12976 KB n=500
32 Correct 3 ms 12892 KB n=500
33 Correct 18 ms 12892 KB n=500
34 Correct 4 ms 12892 KB n=500
35 Correct 16 ms 12888 KB n=500
36 Correct 63 ms 12892 KB n=500
37 Correct 67 ms 12976 KB n=500
38 Correct 64 ms 12888 KB n=500
39 Correct 34 ms 12892 KB n=500
40 Correct 31 ms 12968 KB n=500
41 Correct 32 ms 12984 KB n=500
42 Correct 42 ms 13144 KB n=500
43 Correct 34 ms 12980 KB n=500
44 Correct 31 ms 12892 KB n=500
45 Correct 3 ms 12892 KB n=500
46 Correct 18 ms 12892 KB n=500
47 Correct 14 ms 12888 KB n=500
48 Correct 4 ms 12940 KB n=500
49 Correct 15 ms 12888 KB n=500
50 Correct 4 ms 12888 KB n=500
51 Correct 16 ms 12996 KB n=500
52 Correct 25 ms 12892 KB n=500
53 Correct 12 ms 13144 KB n=500
54 Correct 54 ms 12980 KB n=500
55 Correct 6 ms 12888 KB n=278
56 Correct 128 ms 12976 KB n=500
57 Correct 127 ms 12976 KB n=500
58 Correct 4 ms 12892 KB n=500
59 Correct 5 ms 12892 KB n=2000
60 Correct 342 ms 13148 KB n=2000
61 Correct 320 ms 13112 KB n=2000
62 Correct 212 ms 13084 KB n=2000
63 Correct 6 ms 12888 KB n=2000
64 Correct 291 ms 13096 KB n=2000
65 Correct 5 ms 12892 KB n=2000
66 Correct 377 ms 13116 KB n=2000
67 Correct 8 ms 12972 KB n=2000
68 Correct 301 ms 13104 KB n=2000
69 Correct 1495 ms 13080 KB n=2000
70 Correct 1493 ms 13072 KB n=2000
71 Correct 1535 ms 13152 KB n=2000
72 Correct 702 ms 13076 KB n=2000
73 Correct 703 ms 13140 KB n=2000
74 Correct 5 ms 12892 KB n=1844
75 Correct 745 ms 13324 KB n=2000
76 Correct 766 ms 13136 KB n=2000
77 Correct 757 ms 13060 KB n=2000
78 Correct 821 ms 13064 KB n=2000
79 Correct 5 ms 12888 KB n=2000
80 Correct 287 ms 13128 KB n=2000
81 Correct 267 ms 13140 KB n=2000
82 Correct 7 ms 12888 KB n=2000
83 Correct 280 ms 13116 KB n=2000
84 Correct 7 ms 12892 KB n=2000
85 Correct 210 ms 13280 KB n=2000
86 Correct 151 ms 12892 KB n=2000
87 Correct 8 ms 12888 KB n=2000
88 Correct 3173 ms 13148 KB n=2000
89 Correct 3204 ms 13144 KB n=2000
90 Correct 1255 ms 13148 KB n=2000
91 Correct 12 ms 12888 KB n=2000
92 Correct 617 ms 61396 KB n=200000
93 Execution timed out 4100 ms 61776 KB Time limit exceeded
94 Halted 0 ms 0 KB -