oj.uz

Submission #336217

# Submission time Handle Problem Language Result Execution time Memory
336217 2020-12-15T02:53:45 Z super_j6 Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 35024 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200000, k = __lg(mxn - 1) + 1;
int n, m, q;
int a[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];

void dfs(int c){
	for(int i = 1; i < k; i++) p[i][c] = ~p[i][c] ? p[i - 1][p[i - 1][c]] : -1;
	for(int i : g[c]) if(i != p[0][c]) d[i] = d[c] + 1, p[0][i] = c, dfs(i);
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = k - 1; ~i; i--) if(~p[i][x] && d[p[i][x]] >= d[y]) x = p[i][x];
	for(int i = k - 1; ~i; i--) if(p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
	return x == y ? x : p[0][x];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	p[0][0] = -1;
	dfs(0);
	
	for(int i = 0; i < m; i++) cin >> a[i], a[i]--;
	
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			a[--x] = --y; 
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			l--, r--, x--;
			pi p = {-2, -2};
			for(int i = l; i <= r; i++){
				if(a[i] == x){
					p = {i, i};
					break;
				}else if(i < r && lca(a[i], a[i + 1]) == x){
					p = {i, i + 1};
					break;
				}
			}
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 4 ms 5112 KB n=100
4 Correct 4 ms 5120 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 5 ms 5100 KB n=100
7 Correct 4 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 4 ms 5100 KB n=100
11 Correct 4 ms 5100 KB n=100
12 Correct 4 ms 5120 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 4 ms 5100 KB n=100
15 Correct 3 ms 5100 KB n=100
16 Correct 3 ms 5100 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5100 KB n=100
19 Correct 3 ms 5100 KB n=100
20 Correct 4 ms 5120 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 4 ms 5100 KB n=100
24 Correct 4 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 4 ms 5100 KB n=12
27 Correct 4 ms 5100 KB n=100
28 Correct 4 ms 5228 KB n=500
29 Correct 9 ms 5228 KB n=500
30 Correct 8 ms 5248 KB n=500
31 Correct 9 ms 5228 KB n=500
32 Correct 4 ms 5228 KB n=500
33 Correct 8 ms 5228 KB n=500
34 Correct 4 ms 5228 KB n=500
35 Correct 9 ms 5228 KB n=500
36 Correct 32 ms 5228 KB n=500
37 Correct 32 ms 5228 KB n=500
38 Correct 34 ms 5356 KB n=500
39 Correct 18 ms 5228 KB n=500
40 Correct 17 ms 5228 KB n=500
41 Correct 17 ms 5228 KB n=500
42 Correct 17 ms 5228 KB n=500
43 Correct 17 ms 5228 KB n=500
44 Correct 17 ms 5228 KB n=500
45 Correct 4 ms 5228 KB n=500
46 Correct 9 ms 5228 KB n=500
47 Correct 8 ms 5228 KB n=500
48 Correct 4 ms 5228 KB n=500
49 Correct 8 ms 5228 KB n=500
50 Correct 10 ms 5228 KB n=500
51 Correct 11 ms 5228 KB n=500
52 Correct 13 ms 5228 KB n=500
53 Correct 12 ms 5228 KB n=500
54 Correct 18 ms 5228 KB n=500
55 Correct 4 ms 5228 KB n=278
56 Correct 28 ms 5228 KB n=500
57 Correct 28 ms 5228 KB n=500
58 Correct 25 ms 5228 KB n=500
59 Correct 6 ms 5484 KB n=2000
60 Correct 92 ms 5612 KB n=2000
61 Correct 87 ms 5484 KB n=2000
62 Correct 60 ms 5484 KB n=2000
63 Correct 7 ms 5484 KB n=2000
64 Correct 79 ms 5484 KB n=2000
65 Correct 5 ms 5484 KB n=2000
66 Correct 100 ms 5484 KB n=2000
67 Correct 10 ms 5484 KB n=2000
68 Correct 82 ms 5484 KB n=2000
69 Correct 514 ms 5484 KB n=2000
70 Correct 517 ms 5636 KB n=2000
71 Correct 523 ms 5612 KB n=2000
72 Correct 260 ms 5484 KB n=2000
73 Correct 262 ms 5480 KB n=2000
74 Correct 5 ms 5484 KB n=1844
75 Correct 266 ms 5612 KB n=2000
76 Correct 259 ms 5484 KB n=2000
77 Correct 261 ms 5484 KB n=2000
78 Correct 274 ms 5484 KB n=2000
79 Correct 6 ms 5484 KB n=2000
80 Correct 87 ms 5484 KB n=2000
81 Correct 72 ms 5612 KB n=2000
82 Correct 6 ms 5484 KB n=2000
83 Correct 80 ms 5484 KB n=2000
84 Correct 132 ms 5484 KB n=2000
85 Correct 145 ms 5484 KB n=2000
86 Correct 155 ms 5612 KB n=2000
87 Correct 140 ms 5484 KB n=2000
88 Correct 512 ms 5612 KB n=2000
89 Correct 505 ms 5740 KB n=2000
90 Correct 262 ms 5612 KB n=2000
91 Correct 396 ms 5484 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 4 ms 5112 KB n=100
4 Correct 4 ms 5120 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 5 ms 5100 KB n=100
7 Correct 4 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 4 ms 5100 KB n=100
11 Correct 4 ms 5100 KB n=100
12 Correct 4 ms 5120 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 4 ms 5100 KB n=100
15 Correct 3 ms 5100 KB n=100
16 Correct 3 ms 5100 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5100 KB n=100
19 Correct 3 ms 5100 KB n=100
20 Correct 4 ms 5120 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 4 ms 5100 KB n=100
24 Correct 4 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 4 ms 5100 KB n=12
27 Correct 4 ms 5100 KB n=100
28 Correct 4 ms 5228 KB n=500
29 Correct 9 ms 5228 KB n=500
30 Correct 8 ms 5248 KB n=500
31 Correct 9 ms 5228 KB n=500
32 Correct 4 ms 5228 KB n=500
33 Correct 8 ms 5228 KB n=500
34 Correct 4 ms 5228 KB n=500
35 Correct 9 ms 5228 KB n=500
36 Correct 32 ms 5228 KB n=500
37 Correct 32 ms 5228 KB n=500
38 Correct 34 ms 5356 KB n=500
39 Correct 18 ms 5228 KB n=500
40 Correct 17 ms 5228 KB n=500
41 Correct 17 ms 5228 KB n=500
42 Correct 17 ms 5228 KB n=500
43 Correct 17 ms 5228 KB n=500
44 Correct 17 ms 5228 KB n=500
45 Correct 4 ms 5228 KB n=500
46 Correct 9 ms 5228 KB n=500
47 Correct 8 ms 5228 KB n=500
48 Correct 4 ms 5228 KB n=500
49 Correct 8 ms 5228 KB n=500
50 Correct 10 ms 5228 KB n=500
51 Correct 11 ms 5228 KB n=500
52 Correct 13 ms 5228 KB n=500
53 Correct 12 ms 5228 KB n=500
54 Correct 18 ms 5228 KB n=500
55 Correct 4 ms 5228 KB n=278
56 Correct 28 ms 5228 KB n=500
57 Correct 28 ms 5228 KB n=500
58 Correct 25 ms 5228 KB n=500
59 Correct 6 ms 5484 KB n=2000
60 Correct 92 ms 5612 KB n=2000
61 Correct 87 ms 5484 KB n=2000
62 Correct 60 ms 5484 KB n=2000
63 Correct 7 ms 5484 KB n=2000
64 Correct 79 ms 5484 KB n=2000
65 Correct 5 ms 5484 KB n=2000
66 Correct 100 ms 5484 KB n=2000
67 Correct 10 ms 5484 KB n=2000
68 Correct 82 ms 5484 KB n=2000
69 Correct 514 ms 5484 KB n=2000
70 Correct 517 ms 5636 KB n=2000
71 Correct 523 ms 5612 KB n=2000
72 Correct 260 ms 5484 KB n=2000
73 Correct 262 ms 5480 KB n=2000
74 Correct 5 ms 5484 KB n=1844
75 Correct 266 ms 5612 KB n=2000
76 Correct 259 ms 5484 KB n=2000
77 Correct 261 ms 5484 KB n=2000
78 Correct 274 ms 5484 KB n=2000
79 Correct 6 ms 5484 KB n=2000
80 Correct 87 ms 5484 KB n=2000
81 Correct 72 ms 5612 KB n=2000
82 Correct 6 ms 5484 KB n=2000
83 Correct 80 ms 5484 KB n=2000
84 Correct 132 ms 5484 KB n=2000
85 Correct 145 ms 5484 KB n=2000
86 Correct 155 ms 5612 KB n=2000
87 Correct 140 ms 5484 KB n=2000
88 Correct 512 ms 5612 KB n=2000
89 Correct 505 ms 5740 KB n=2000
90 Correct 262 ms 5612 KB n=2000
91 Correct 396 ms 5484 KB n=2000
92 Execution timed out 4062 ms 35024 KB Time limit exceeded
93 Halted 0 ms 0 KB -