oj.uz

Submission #379406

# Submission time Handle Problem Language Result Execution time Memory
379406 2021-03-18T07:07:44 Z rk42745417 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1315 ms 83564 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 2e5 + 25, LGN = 19;
vector<int> edge[N];
int anc[LGN][N], dep[N];

void dfs(int u, int p) {
	for(int v : edge[u])
		if(v != p)
			dep[v] = dep[u] + 1, anc[0][v] = u, dfs(v, u);
}
int lca(int a, int b) {
	if(dep[a] < dep[b])
		swap(a, b);
	for(int i = 0, x = dep[a] - dep[b]; i < LGN; i++)
		if(x >> i & 1)
			a = anc[i][a];
	if(a == b)
		return a;
	for(int i = LGN - 1; ~i; i--) {
		if(anc[i][a] != anc[i][b]) {
			a = anc[i][a];
			b = anc[i][b];
		}
	}
	return anc[0][a];
}

set<int> one[N], two[N];

signed main() { EmiliaMyWife
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs(1, 1);
	for(int i = 1; i < LGN; i++)
		for(int j = 1; j <= n; j++)
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
	vector<int> arr(m + 1);
	for(int i = 1; i <= m; i++)
		cin >> arr[i], one[arr[i]].insert(i);
	for(int i = 2; i <= m; i++)
		two[lca(arr[i - 1], arr[i])].insert(i - 1);
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int p, v;
			cin >> p >> v;
			one[arr[p]].erase(p);
			if(p > 1)
				two[lca(arr[p - 1], arr[p])].erase(p - 1);
			if(p + 1 <= m)
				two[lca(arr[p], arr[p + 1])].erase(p);
			arr[p] = v;
			one[arr[p]].insert(p);
			if(p > 1)
				two[lca(arr[p - 1], arr[p])].insert(p - 1);
			if(p + 1 <= m)
				two[lca(arr[p], arr[p + 1])].insert(p);
		}
		else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it = one[v].lower_bound(l);
			auto it2 = two[v].lower_bound(l);
			if(it != one[v].end() && *it <= r)
				cout << *it << ' ' << *it << '\n';
			else if(it2 != two[v].end() && *it2 < r)
				cout << *it2 << ' ' << *it2 + 1 << '\n';
			else
				cout << "-1 -1\n";
		}
	}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

*/

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 16 ms 23916 KB n=100
4 Correct 16 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 16 ms 23916 KB n=100
7 Correct 16 ms 23916 KB n=100
8 Correct 17 ms 23916 KB n=100
9 Correct 16 ms 23916 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23940 KB n=100
12 Correct 16 ms 23936 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 16 ms 23916 KB n=100
15 Correct 17 ms 23916 KB n=100
16 Correct 17 ms 23916 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 18 ms 23916 KB n=100
19 Correct 16 ms 23916 KB n=100
20 Correct 16 ms 23916 KB n=100
21 Correct 16 ms 23916 KB n=100
22 Correct 17 ms 23916 KB n=100
23 Correct 17 ms 23948 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 16 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 24044 KB n=500
29 Correct 17 ms 24044 KB n=500
30 Correct 17 ms 24044 KB n=500
31 Correct 17 ms 24044 KB n=500
32 Correct 17 ms 24044 KB n=500
33 Correct 17 ms 24044 KB n=500
34 Correct 18 ms 24192 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 17 ms 24044 KB n=500
37 Correct 17 ms 24044 KB n=500
38 Correct 17 ms 24044 KB n=500
39 Correct 18 ms 24044 KB n=500
40 Correct 17 ms 24044 KB n=500
41 Correct 17 ms 24044 KB n=500
42 Correct 17 ms 24044 KB n=500
43 Correct 17 ms 24044 KB n=500
44 Correct 17 ms 24044 KB n=500
45 Correct 17 ms 24044 KB n=500
46 Correct 17 ms 24044 KB n=500
47 Correct 17 ms 24044 KB n=500
48 Correct 17 ms 24044 KB n=500
49 Correct 17 ms 24044 KB n=500
50 Correct 17 ms 24172 KB n=500
51 Correct 17 ms 24044 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 17 ms 24044 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 24044 KB n=278
56 Correct 17 ms 24044 KB n=500
57 Correct 18 ms 24172 KB n=500
58 Correct 17 ms 24044 KB n=500
59 Correct 20 ms 24428 KB n=2000
60 Correct 20 ms 24556 KB n=2000
61 Correct 20 ms 24428 KB n=2000
62 Correct 20 ms 24428 KB n=2000
63 Correct 20 ms 24428 KB n=2000
64 Correct 20 ms 24428 KB n=2000
65 Correct 20 ms 24428 KB n=2000
66 Correct 20 ms 24556 KB n=2000
67 Correct 20 ms 24428 KB n=2000
68 Correct 20 ms 24556 KB n=2000
69 Correct 19 ms 24428 KB n=2000
70 Correct 19 ms 24428 KB n=2000
71 Correct 20 ms 24428 KB n=2000
72 Correct 22 ms 24428 KB n=2000
73 Correct 19 ms 24428 KB n=2000
74 Correct 22 ms 24428 KB n=1844
75 Correct 19 ms 24428 KB n=2000
76 Correct 20 ms 24428 KB n=2000
77 Correct 20 ms 24428 KB n=2000
78 Correct 20 ms 24428 KB n=2000
79 Correct 20 ms 24428 KB n=2000
80 Correct 20 ms 24556 KB n=2000
81 Correct 20 ms 24428 KB n=2000
82 Correct 20 ms 24428 KB n=2000
83 Correct 20 ms 24556 KB n=2000
84 Correct 20 ms 24428 KB n=2000
85 Correct 20 ms 24520 KB n=2000
86 Correct 20 ms 24428 KB n=2000
87 Correct 21 ms 24428 KB n=2000
88 Correct 20 ms 24556 KB n=2000
89 Correct 20 ms 24576 KB n=2000
90 Correct 20 ms 24684 KB n=2000
91 Correct 19 ms 24428 KB n=2000
92 Correct 976 ms 72044 KB n=200000
93 Correct 1191 ms 77420 KB n=200000
94 Correct 1095 ms 81772 KB n=200000
95 Correct 980 ms 72032 KB n=200000
96 Correct 983 ms 72160 KB n=200000
97 Correct 1240 ms 76176 KB n=200000
98 Correct 981 ms 72160 KB n=200000
99 Correct 1227 ms 71536 KB n=200000
100 Correct 971 ms 72420 KB n=200000
101 Correct 1103 ms 83564 KB n=200000
102 Correct 520 ms 73068 KB n=200000
103 Correct 517 ms 73004 KB n=200000
104 Correct 524 ms 72944 KB n=200000
105 Correct 524 ms 72812 KB n=200000
106 Correct 509 ms 72684 KB n=200000
107 Correct 541 ms 72684 KB n=200000
108 Correct 1082 ms 71404 KB n=200000
109 Correct 1079 ms 71084 KB n=200000
110 Correct 1072 ms 70764 KB n=200000
111 Correct 931 ms 71012 KB n=200000
112 Correct 1070 ms 81260 KB n=200000
113 Correct 1179 ms 75244 KB n=200000
114 Correct 924 ms 71264 KB n=200000
115 Correct 1315 ms 72684 KB n=200000
116 Correct 876 ms 71140 KB n=200000
117 Correct 1062 ms 81732 KB n=200000
118 Correct 1191 ms 73708 KB n=200000
119 Correct 879 ms 70880 KB n=200000
120 Correct 1000 ms 82284 KB n=200000
121 Correct 1022 ms 82492 KB n=200000
122 Correct 1008 ms 83052 KB n=200000
123 Correct 516 ms 71404 KB n=200000
124 Correct 260 ms 39080 KB n=25264