oj.uz

Submission #336295

# Submission time Handle Problem Language Result Execution time Memory
336295 2020-12-15T03:52:12 Z super_j6 Birthday gift (IZhO18_treearray) C++14
56 / 100
 206 ms 73708 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
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, w = 700;
int n, m, q;
int a[mxn], lc[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];
set<pi> s[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];
		s[--a[i]].insert({i, i});
		if(i) s[lc[i - 1] = lca(a[i - 1], a[i])].insert({i - 1, i});
	} 
	
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			x--, y--;
			s[a[x]].erase({x, x});
			if(x) s[lc[x - 1]].erase({x - 1, x});
			if(x < m - 1) s[lc[x]].erase({x, x + 1});
			
			s[a[x] = y].insert({x, x});
			if(x) s[lc[x - 1] = lca(a[x - 1], a[x])].insert({x - 1, x});
			if(x < m - 1) s[lc[x] = lca(a[x], a[x + 1])].insert({x, x + 1});
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			l--, r--, x--;
			auto it = s[x].lower_bound({l, l});
			pi p = it != s[x].end() && it->s <= r ? *it : pi{-2, -2};
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14572 KB n=5
2 Correct 9 ms 14572 KB n=100
3 Correct 9 ms 14572 KB n=100
4 Correct 10 ms 14572 KB n=100
5 Correct 9 ms 14572 KB n=100
6 Correct 9 ms 14572 KB n=100
7 Correct 9 ms 14572 KB n=100
8 Correct 9 ms 14572 KB n=100
9 Correct 9 ms 14572 KB n=100
10 Correct 9 ms 14572 KB n=100
11 Correct 9 ms 14572 KB n=100
12 Correct 9 ms 14572 KB n=100
13 Correct 10 ms 14700 KB n=100
14 Correct 10 ms 14572 KB n=100
15 Correct 10 ms 14720 KB n=100
16 Correct 10 ms 14572 KB n=100
17 Correct 10 ms 14572 KB n=100
18 Correct 10 ms 14572 KB n=100
19 Correct 10 ms 14572 KB n=100
20 Correct 10 ms 14592 KB n=100
21 Correct 10 ms 14572 KB n=100
22 Correct 10 ms 14572 KB n=100
23 Correct 10 ms 14572 KB n=100
24 Correct 9 ms 14592 KB n=100
25 Correct 9 ms 14572 KB n=100
26 Correct 11 ms 14572 KB n=12
27 Correct 9 ms 14572 KB n=100
28 Correct 10 ms 14700 KB n=500
29 Correct 10 ms 14700 KB n=500
30 Correct 11 ms 14700 KB n=500
31 Correct 10 ms 14700 KB n=500
32 Correct 10 ms 14700 KB n=500
33 Correct 10 ms 14700 KB n=500
34 Correct 12 ms 14700 KB n=500
35 Correct 10 ms 14700 KB n=500
36 Correct 10 ms 14700 KB n=500
37 Correct 10 ms 14700 KB n=500
38 Correct 10 ms 14700 KB n=500
39 Correct 10 ms 14700 KB n=500
40 Correct 10 ms 14700 KB n=500
41 Correct 10 ms 14700 KB n=500
42 Correct 13 ms 14700 KB n=500
43 Correct 11 ms 14700 KB n=500
44 Correct 11 ms 14700 KB n=500
45 Correct 10 ms 14700 KB n=500
46 Correct 11 ms 14700 KB n=500
47 Correct 10 ms 14700 KB n=500
48 Correct 10 ms 14700 KB n=500
49 Correct 10 ms 14700 KB n=500
50 Correct 10 ms 14700 KB n=500
51 Correct 12 ms 14700 KB n=500
52 Correct 11 ms 14700 KB n=500
53 Correct 12 ms 14700 KB n=500
54 Correct 11 ms 14700 KB n=500
55 Correct 10 ms 14572 KB n=278
56 Correct 13 ms 14700 KB n=500
57 Correct 10 ms 14700 KB n=500
58 Correct 10 ms 14700 KB n=500
59 Correct 16 ms 14956 KB n=2000
60 Correct 14 ms 15084 KB n=2000
61 Correct 14 ms 15084 KB n=2000
62 Correct 14 ms 14976 KB n=2000
63 Correct 14 ms 14976 KB n=2000
64 Correct 14 ms 14956 KB n=2000
65 Correct 14 ms 14956 KB n=2000
66 Correct 14 ms 15084 KB n=2000
67 Correct 14 ms 15084 KB n=2000
68 Correct 13 ms 14956 KB n=2000
69 Correct 15 ms 14956 KB n=2000
70 Correct 13 ms 14956 KB n=2000
71 Correct 13 ms 14956 KB n=2000
72 Correct 13 ms 14956 KB n=2000
73 Correct 13 ms 14956 KB n=2000
74 Correct 13 ms 14956 KB n=1844
75 Correct 13 ms 14956 KB n=2000
76 Correct 14 ms 14956 KB n=2000
77 Correct 14 ms 14956 KB n=2000
78 Correct 14 ms 14976 KB n=2000
79 Correct 14 ms 14956 KB n=2000
80 Correct 16 ms 15084 KB n=2000
81 Correct 14 ms 14956 KB n=2000
82 Correct 13 ms 14956 KB n=2000
83 Correct 14 ms 15084 KB n=2000
84 Correct 15 ms 14956 KB n=2000
85 Correct 16 ms 14956 KB n=2000
86 Correct 16 ms 14956 KB n=2000
87 Correct 14 ms 14956 KB n=2000
88 Correct 13 ms 15084 KB n=2000
89 Correct 13 ms 15084 KB n=2000
90 Correct 13 ms 15084 KB n=2000
91 Correct 13 ms 14956 KB n=2000
92 Runtime error 206 ms 73708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Halted 0 ms 0 KB -