oj.uz

Submission #341957

# Submission time Handle Problem Language Result Execution time Memory
341957 2020-12-31T18:55:00 Z Tosic Birthday gift (IZhO18_treearray) C++14
100 / 100
 1222 ms 77420 KB 
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;

int n, m, q;
int up[maxn][20],iT[maxn], oT[maxn], gT, a[maxn];
vector<vector<int> > gr;
set<int> allNum[maxn], allPai[maxn];

void dfs(int x, int p){
	iT[x] = gT;
	++gT;
	up[x][0] = p;
	for(int i =1 ; i < 20; ++i){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(auto i : gr[x]){
		if(i != p){
			dfs(i, x);
		}
	}
	oT[x] = gT;
	++gT;
}

bool isA(int a, int b){
	if(iT[a] <= iT[b] and oT[a] >= oT[b]){
		return true;
	}
	return 0;
}

int lca(int x, int y){
	if(isA(x, y)){
		return x;
	}
	if(isA(y, x)){
		return y;
	}
	for(int i = 19; i >= 0; --i){
		if(!isA(up[x][i], y)){
			x = up[x][i];
		}
	}
	return up[x][0];
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m >> q;
	gr.resize(n, vector<int>());
	for(int i = 1; i < n; ++i){
		int u,v;
		cin >> u >> v;
		--u, v--;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	dfs(0, 0);
	for(int i = 0; i < m; ++i){
		cin >> a[i];
		--a[i];
		allNum[a[i]].insert(i);
		if(i){
			allPai[lca(a[i], a[i-1])].insert(i);
		}
	}
	for(int i = 0; i < q; ++i){
		int t;
		cin >> t;
		if(t == 1){
			int ps, val;
			cin >> ps >> val;
			--ps;
			--val;
			allNum[a[ps]].erase(ps);
			if(ps){
				allPai[lca(a[ps-1], a[ps])].erase(ps);
				allPai[lca(a[ps-1], val)].insert(ps);
			}
			if(ps < m-1){
				allPai[lca(a[ps+1], a[ps])].erase(ps+1);
				allPai[lca(a[ps+1], val)].insert(ps+1);
			}
			a[ps] = val;
			allNum[val].insert(ps);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			--l, --r, --v;
			auto tmp = allNum[v].lower_bound(l);
			if(tmp != allNum[v].end() and *tmp <= r){
				cout << *tmp+1 << ' ' << *tmp+1 << '\n';
				continue;
			}
			tmp=allPai[v].upper_bound(l);
			if(tmp != allPai[v].end() and *tmp <= r){
				cout << *tmp << ' ' << *tmp+1<<'\n';
				continue;
			}
			cout <<"-1 -1\n";
		}
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19180 KB n=5
2 Correct 13 ms 19180 KB n=100
3 Correct 13 ms 19180 KB n=100
4 Correct 13 ms 19180 KB n=100
5 Correct 13 ms 19180 KB n=100
6 Correct 13 ms 19180 KB n=100
7 Correct 13 ms 19180 KB n=100
8 Correct 13 ms 19180 KB n=100
9 Correct 13 ms 19224 KB n=100
10 Correct 13 ms 19180 KB n=100
11 Correct 13 ms 19180 KB n=100
12 Correct 13 ms 19200 KB n=100
13 Correct 13 ms 19180 KB n=100
14 Correct 13 ms 19216 KB n=100
15 Correct 13 ms 19180 KB n=100
16 Correct 13 ms 19180 KB n=100
17 Correct 13 ms 19180 KB n=100
18 Correct 13 ms 19180 KB n=100
19 Correct 13 ms 19180 KB n=100
20 Correct 13 ms 19180 KB n=100
21 Correct 13 ms 19180 KB n=100
22 Correct 13 ms 19180 KB n=100
23 Correct 13 ms 19180 KB n=100
24 Correct 13 ms 19180 KB n=100
25 Correct 13 ms 19180 KB n=100
26 Correct 13 ms 19180 KB n=12
27 Correct 13 ms 19180 KB n=100
28 Correct 14 ms 19308 KB n=500
29 Correct 14 ms 19308 KB n=500
30 Correct 14 ms 19308 KB n=500
31 Correct 14 ms 19308 KB n=500
32 Correct 14 ms 19308 KB n=500
33 Correct 14 ms 19308 KB n=500
34 Correct 14 ms 19308 KB n=500
35 Correct 13 ms 19308 KB n=500
36 Correct 14 ms 19308 KB n=500
37 Correct 14 ms 19308 KB n=500
38 Correct 14 ms 19308 KB n=500
39 Correct 16 ms 19308 KB n=500
40 Correct 14 ms 19308 KB n=500
41 Correct 13 ms 19308 KB n=500
42 Correct 14 ms 19308 KB n=500
43 Correct 14 ms 19308 KB n=500
44 Correct 14 ms 19308 KB n=500
45 Correct 14 ms 19308 KB n=500
46 Correct 14 ms 19308 KB n=500
47 Correct 15 ms 19308 KB n=500
48 Correct 14 ms 19308 KB n=500
49 Correct 14 ms 19308 KB n=500
50 Correct 14 ms 19308 KB n=500
51 Correct 14 ms 19308 KB n=500
52 Correct 14 ms 19308 KB n=500
53 Correct 14 ms 19252 KB n=500
54 Correct 14 ms 19308 KB n=500
55 Correct 14 ms 19180 KB n=278
56 Correct 14 ms 19308 KB n=500
57 Correct 14 ms 19308 KB n=500
58 Correct 14 ms 19308 KB n=500
59 Correct 18 ms 19692 KB n=2000
60 Correct 16 ms 19692 KB n=2000
61 Correct 16 ms 19692 KB n=2000
62 Correct 17 ms 19692 KB n=2000
63 Correct 17 ms 19692 KB n=2000
64 Correct 17 ms 19692 KB n=2000
65 Correct 17 ms 19692 KB n=2000
66 Correct 16 ms 19692 KB n=2000
67 Correct 17 ms 19692 KB n=2000
68 Correct 17 ms 19692 KB n=2000
69 Correct 16 ms 19692 KB n=2000
70 Correct 16 ms 19692 KB n=2000
71 Correct 16 ms 19692 KB n=2000
72 Correct 16 ms 19692 KB n=2000
73 Correct 16 ms 19692 KB n=2000
74 Correct 16 ms 19564 KB n=1844
75 Correct 16 ms 19692 KB n=2000
76 Correct 17 ms 19692 KB n=2000
77 Correct 17 ms 19692 KB n=2000
78 Correct 17 ms 19692 KB n=2000
79 Correct 17 ms 19692 KB n=2000
80 Correct 16 ms 19692 KB n=2000
81 Correct 16 ms 19692 KB n=2000
82 Correct 17 ms 19692 KB n=2000
83 Correct 16 ms 19692 KB n=2000
84 Correct 17 ms 19692 KB n=2000
85 Correct 17 ms 19692 KB n=2000
86 Correct 17 ms 19692 KB n=2000
87 Correct 17 ms 19692 KB n=2000
88 Correct 16 ms 19692 KB n=2000
89 Correct 16 ms 19692 KB n=2000
90 Correct 16 ms 19692 KB n=2000
91 Correct 16 ms 19692 KB n=2000
92 Correct 871 ms 69064 KB n=200000
93 Correct 931 ms 72812 KB n=200000
94 Correct 702 ms 76012 KB n=200000
95 Correct 853 ms 68832 KB n=200000
96 Correct 789 ms 68760 KB n=200000
97 Correct 1012 ms 71916 KB n=200000
98 Correct 826 ms 69088 KB n=200000
99 Correct 1038 ms 68592 KB n=200000
100 Correct 819 ms 68980 KB n=200000
101 Correct 627 ms 77164 KB n=200000
102 Correct 510 ms 69740 KB n=200000
103 Correct 512 ms 69740 KB n=200000
104 Correct 509 ms 69740 KB n=200000
105 Correct 515 ms 69484 KB n=200000
106 Correct 517 ms 69484 KB n=200000
107 Correct 509 ms 69484 KB n=200000
108 Correct 930 ms 68716 KB n=200000
109 Correct 916 ms 68460 KB n=200000
110 Correct 901 ms 68716 KB n=200000
111 Correct 864 ms 68836 KB n=200000
112 Correct 658 ms 76140 KB n=200000
113 Correct 977 ms 71916 KB n=200000
114 Correct 869 ms 68832 KB n=200000
115 Correct 1222 ms 69868 KB n=200000
116 Correct 786 ms 68576 KB n=200000
117 Correct 631 ms 76524 KB n=200000
118 Correct 1100 ms 70508 KB n=200000
119 Correct 794 ms 68448 KB n=200000
120 Correct 559 ms 76908 KB n=200000
121 Correct 559 ms 76908 KB n=200000
122 Correct 575 ms 77420 KB n=200000
123 Correct 534 ms 69136 KB n=200000
124 Correct 214 ms 32876 KB n=25264