oj.uz

Submission #217860

# Submission time Handle Problem Language Result Execution time Memory
217860 2020-03-31T04:53:59 Z socho Birthday gift (IZhO18_treearray) C++14
100 / 100
 1762 ms 77024 KB 
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000 + 7;
// int MOD = 998244353;

int n, m, q;
const int MXN = 200005, MXK = 20;
vector<int> adj[MXN];

int par[MXN][MXK];
int depth[MXN];

void dfs_par(int node, int last, int dep) {
	depth[node] = dep;
	par[node][0] = last;
	for (int i=1; i<MXK; i++) {
		int op = par[node][i-1];
		if (op != -1) {
			par[node][i] = par[op][i-1];
		}
	}
	for (int i=0; i<adj[node].size(); i++) {
		int o = adj[node][i];
		if (o == last) continue;
		dfs_par(o, node, dep+1);
	}
}

int kth_parent(int n, int k) {
	for (int i=0; i<MXK; i++) {
		if (k & (1 << i)) {
			n = par[n][i];
		}
	}
	return n;
}

int lca(int a, int b) {
	if (depth[a] > depth[b]) swap(a, b);
	b = kth_parent(b, depth[b] - depth[a]);
	if (a == b) return a;
	for (int i=MXK-1; i>=0; i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}


signed main() {
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = -1;
	
	cin >> n >> m >> q;
	for (int i=0; i<n-1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs_par(1, -1, 0);
	
	set<int> occ[n+1], loc[n+1];
	
	int arr[m];
	for (int i=0; i<m; i++) {
		cin >> arr[i];
		occ[arr[i]].insert(i);
	}
	
	int imm_lca[m-1];
	for (int i=0; i<m-1; i++) {
		imm_lca[i] = lca(arr[i], arr[i+1]);
		loc[imm_lca[i]].insert(i);
	}
	
	for (int i=0; i<q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int pos, to;
			cin >> pos >> to;
			pos--;
			int f = arr[pos];
			occ[f].erase(pos);
			occ[to].insert(pos);
			arr[pos] = to;
			if (pos > 0) {
				// can try before
				int pr = imm_lca[pos-1];
				loc[pr].erase(pos-1);
				imm_lca[pos-1] = lca(arr[pos-1], to);
				loc[imm_lca[pos-1]].insert(pos-1);
			}
			if (pos < m-1) {
				// can try after
				int pr = imm_lca[pos];
				loc[pr].erase(pos);
				imm_lca[pos] = lca(to, arr[pos+1]);
				loc[imm_lca[pos]].insert(pos);
			}
			
		}
		else {
			int l, r, w;
			cin >> l >> r >> w;
			l--; r--;
			set<int>::iterator x = occ[w].lower_bound(l);
			if (x == occ[w].end() || *x > r) {
				// cant use same one
				x = loc[w].lower_bound(l);
				if (x == loc[w].end() || *x >= r) {
					cout << -1 << ' ' << -1 << endl;
				}
				else {
					int f = *x;
					cout << f+1 << ' ' << f+2 << endl;
				}
			}
			else {
				int f = *x;
				cout << f+1 << ' ' << f+1 << endl;
			}
		}
	}
	
}

Compilation message

treearray.cpp: In function 'void dfs_par(int, int, int)':
treearray.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20608 KB n=5
2 Correct 16 ms 20736 KB n=100
3 Correct 16 ms 20736 KB n=100
4 Correct 16 ms 20736 KB n=100
5 Correct 16 ms 20736 KB n=100
6 Correct 16 ms 20736 KB n=100
7 Correct 16 ms 20736 KB n=100
8 Correct 16 ms 20736 KB n=100
9 Correct 18 ms 20736 KB n=100
10 Correct 16 ms 20736 KB n=100
11 Correct 16 ms 20736 KB n=100
12 Correct 16 ms 20736 KB n=100
13 Correct 16 ms 20736 KB n=100
14 Correct 16 ms 20736 KB n=100
15 Correct 16 ms 20736 KB n=100
16 Correct 18 ms 20736 KB n=100
17 Correct 16 ms 20736 KB n=100
18 Correct 16 ms 20736 KB n=100
19 Correct 15 ms 20736 KB n=100
20 Correct 16 ms 20736 KB n=100
21 Correct 16 ms 20736 KB n=100
22 Correct 18 ms 20736 KB n=100
23 Correct 16 ms 20736 KB n=100
24 Correct 16 ms 20736 KB n=100
25 Correct 16 ms 20736 KB n=100
26 Correct 16 ms 20736 KB n=12
27 Correct 16 ms 20736 KB n=100
28 Correct 18 ms 20736 KB n=500
29 Correct 18 ms 20864 KB n=500
30 Correct 18 ms 20864 KB n=500
31 Correct 17 ms 20864 KB n=500
32 Correct 17 ms 20736 KB n=500
33 Correct 17 ms 20736 KB n=500
34 Correct 17 ms 20732 KB n=500
35 Correct 18 ms 20864 KB n=500
36 Correct 18 ms 20736 KB n=500
37 Correct 18 ms 20736 KB n=500
38 Correct 18 ms 20864 KB n=500
39 Correct 19 ms 20736 KB n=500
40 Correct 18 ms 20736 KB n=500
41 Correct 18 ms 20864 KB n=500
42 Correct 17 ms 20736 KB n=500
43 Correct 18 ms 20736 KB n=500
44 Correct 18 ms 20736 KB n=500
45 Correct 18 ms 20736 KB n=500
46 Correct 18 ms 20736 KB n=500
47 Correct 18 ms 20736 KB n=500
48 Correct 17 ms 20736 KB n=500
49 Correct 17 ms 20736 KB n=500
50 Correct 18 ms 20864 KB n=500
51 Correct 18 ms 20736 KB n=500
52 Correct 18 ms 20864 KB n=500
53 Correct 19 ms 20736 KB n=500
54 Correct 18 ms 20736 KB n=500
55 Correct 16 ms 20736 KB n=278
56 Correct 18 ms 20736 KB n=500
57 Correct 18 ms 20736 KB n=500
58 Correct 18 ms 20736 KB n=500
59 Correct 23 ms 21248 KB n=2000
60 Correct 24 ms 21248 KB n=2000
61 Correct 24 ms 21152 KB n=2000
62 Correct 25 ms 21248 KB n=2000
63 Correct 24 ms 21120 KB n=2000
64 Correct 24 ms 21248 KB n=2000
65 Correct 26 ms 21248 KB n=2000
66 Correct 24 ms 21248 KB n=2000
67 Correct 24 ms 21248 KB n=2000
68 Correct 24 ms 21248 KB n=2000
69 Correct 25 ms 21248 KB n=2000
70 Correct 26 ms 21248 KB n=2000
71 Correct 26 ms 21248 KB n=2000
72 Correct 25 ms 21248 KB n=2000
73 Correct 25 ms 21248 KB n=2000
74 Correct 23 ms 21120 KB n=1844
75 Correct 25 ms 21248 KB n=2000
76 Correct 24 ms 21248 KB n=2000
77 Correct 24 ms 21248 KB n=2000
78 Correct 25 ms 21248 KB n=2000
79 Correct 24 ms 21248 KB n=2000
80 Correct 25 ms 21248 KB n=2000
81 Correct 25 ms 21248 KB n=2000
82 Correct 24 ms 21376 KB n=2000
83 Correct 24 ms 21248 KB n=2000
84 Correct 24 ms 21248 KB n=2000
85 Correct 24 ms 21248 KB n=2000
86 Correct 24 ms 21240 KB n=2000
87 Correct 24 ms 21248 KB n=2000
88 Correct 24 ms 21248 KB n=2000
89 Correct 24 ms 21248 KB n=2000
90 Correct 23 ms 21248 KB n=2000
91 Correct 26 ms 21248 KB n=2000
92 Correct 1384 ms 75308 KB n=200000
93 Correct 1669 ms 75768 KB n=200000
94 Correct 1639 ms 76020 KB n=200000
95 Correct 1393 ms 75220 KB n=200000
96 Correct 1370 ms 75304 KB n=200000
97 Correct 1667 ms 75768 KB n=200000
98 Correct 1351 ms 75500 KB n=200000
99 Correct 1564 ms 75756 KB n=200000
100 Correct 1391 ms 75276 KB n=200000
101 Correct 1581 ms 75768 KB n=200000
102 Correct 1267 ms 76444 KB n=200000
103 Correct 1256 ms 76616 KB n=200000
104 Correct 1262 ms 76536 KB n=200000
105 Correct 1294 ms 77024 KB n=200000
106 Correct 1307 ms 76816 KB n=200000
107 Correct 1318 ms 76996 KB n=200000
108 Correct 1572 ms 75512 KB n=200000
109 Correct 1469 ms 75368 KB n=200000
110 Correct 1486 ms 75500 KB n=200000
111 Correct 1382 ms 74788 KB n=200000
112 Correct 1575 ms 75744 KB n=200000
113 Correct 1633 ms 75880 KB n=200000
114 Correct 1412 ms 74708 KB n=200000
115 Correct 1762 ms 75668 KB n=200000
116 Correct 1337 ms 75624 KB n=200000
117 Correct 1598 ms 75468 KB n=200000
118 Correct 1669 ms 75556 KB n=200000
119 Correct 1331 ms 75368 KB n=200000
120 Correct 1531 ms 74560 KB n=200000
121 Correct 1533 ms 74744 KB n=200000
122 Correct 1524 ms 74884 KB n=200000
123 Correct 1314 ms 76664 KB n=200000
124 Correct 449 ms 35400 KB n=25264