oj.uz

Submission #914222

# Submission time Handle Problem Language Result Execution time Memory
914222 2024-01-21T11:34:15 Z AlphaMale06 Birthday gift (IZhO18_treearray) C++14
100 / 100
 2420 ms 85548 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

const int N = 2e5+3;
vector<int> adj[N];
int p[18][N];
int tin[N], tout[N];
int timer=-1;
set<pair<int, int>> st;
set<pair<int, int>> st2;

void dfs(int v, int par){
	tin[v]=++timer;
	p[0][v]=par;
	for(int i=1; i<18; i++){
		p[i][v]=p[i-1][p[i-1][v]];
	}
	for(int to : adj[v]){
		if(to!=par)dfs(to, v);
	}
	tout[v]=timer;
}

bool isanc(int u, int v){
	return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca(int u, int v){
	if(isanc(u, v))return u;
	if(isanc(v, u))return v;
	int ret=u;
	for(int i=17; i>=0; i--){
		if(!isanc(p[i][ret], v)){
			ret=p[i][ret];
		}
	}
	return p[0][ret];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0; i< n-1; i++){
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	dfs(1, 0);	
	tin[0]=0; tout[0]=1e9;
	int a[m];
	for(int i=0; i< m; i++){
		cin >> a[i];
		st.insert({a[i], i});
	}
	for(int i=0; i< m-1; i++){
		st2.insert({lca(a[i], a[i+1]), i});
	}
	while(q--){
		int t;
		cin >> t;
		if(t==1){
			int pos, v;
			cin >> pos >> v;
			pos--;
			st.erase({a[pos], pos});
			if(pos!=0){
				st2.erase({lca(a[pos-1], a[pos]), pos-1});
			}
			if(pos!=m-1){
				st2.erase({lca(a[pos], a[pos+1]), pos});
			}
			a[pos]=v;
			st.insert({a[pos], pos});
			if(pos!=0){
				st2.insert({lca(a[pos-1], a[pos]), pos-1});
			}
			if(pos!=m-1){
				st2.insert({lca(a[pos], a[pos+1]), pos});
			}
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			l--; r--;
			auto ptr=st.lower_bound({v, l});
			if(ptr!=st.end()){
				pair<int, int> ans = *ptr;
				if(ans.F==v && ans.S<=r){
					cout << ans.S+1 << " " << ans.S+1 << '\n';
					continue;
				}	
			}
			ptr=st2.lower_bound({v, l});
			if(ptr!=st2.end()){
				pair<int, int> ans = *ptr;
				if(ans.F==v && ans.S<r){
					cout << ans.S+1 << " " << ans.S+2 << '\n';
					continue;
				}
			}
			cout << "-1 -1\n";
		}
	}
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 36184 KB n=5
2 Correct 8 ms 36240 KB n=100
3 Correct 7 ms 36188 KB n=100
4 Correct 7 ms 36236 KB n=100
5 Correct 7 ms 36232 KB n=100
6 Correct 7 ms 36188 KB n=100
7 Correct 7 ms 36184 KB n=100
8 Correct 6 ms 36184 KB n=100
9 Correct 6 ms 36188 KB n=100
10 Correct 7 ms 36184 KB n=100
11 Correct 8 ms 36184 KB n=100
12 Correct 7 ms 36188 KB n=100
13 Correct 7 ms 36188 KB n=100
14 Correct 6 ms 36188 KB n=100
15 Correct 6 ms 36188 KB n=100
16 Correct 6 ms 36184 KB n=100
17 Correct 7 ms 36188 KB n=100
18 Correct 8 ms 36284 KB n=100
19 Correct 7 ms 36444 KB n=100
20 Correct 6 ms 36188 KB n=100
21 Correct 6 ms 36232 KB n=100
22 Correct 7 ms 36184 KB n=100
23 Correct 7 ms 36184 KB n=100
24 Correct 7 ms 36188 KB n=100
25 Correct 6 ms 36236 KB n=100
26 Correct 6 ms 36248 KB n=12
27 Correct 7 ms 36188 KB n=100
28 Correct 8 ms 36188 KB n=500
29 Correct 8 ms 36184 KB n=500
30 Correct 8 ms 36188 KB n=500
31 Correct 8 ms 36188 KB n=500
32 Correct 7 ms 36184 KB n=500
33 Correct 7 ms 36188 KB n=500
34 Correct 7 ms 36184 KB n=500
35 Correct 7 ms 36184 KB n=500
36 Correct 7 ms 36344 KB n=500
37 Correct 8 ms 36300 KB n=500
38 Correct 7 ms 36188 KB n=500
39 Correct 8 ms 36312 KB n=500
40 Correct 7 ms 36188 KB n=500
41 Correct 7 ms 36184 KB n=500
42 Correct 7 ms 36188 KB n=500
43 Correct 7 ms 36188 KB n=500
44 Correct 8 ms 36188 KB n=500
45 Correct 7 ms 36184 KB n=500
46 Correct 7 ms 36184 KB n=500
47 Correct 8 ms 36188 KB n=500
48 Correct 7 ms 36188 KB n=500
49 Correct 8 ms 36184 KB n=500
50 Correct 8 ms 36188 KB n=500
51 Correct 7 ms 36188 KB n=500
52 Correct 8 ms 36184 KB n=500
53 Correct 7 ms 36188 KB n=500
54 Correct 7 ms 36188 KB n=500
55 Correct 7 ms 36184 KB n=278
56 Correct 7 ms 36188 KB n=500
57 Correct 7 ms 36188 KB n=500
58 Correct 7 ms 36188 KB n=500
59 Correct 11 ms 36700 KB n=2000
60 Correct 9 ms 36764 KB n=2000
61 Correct 11 ms 36696 KB n=2000
62 Correct 10 ms 36700 KB n=2000
63 Correct 10 ms 36532 KB n=2000
64 Correct 9 ms 36700 KB n=2000
65 Correct 10 ms 36700 KB n=2000
66 Correct 9 ms 36700 KB n=2000
67 Correct 9 ms 36652 KB n=2000
68 Correct 10 ms 36700 KB n=2000
69 Correct 9 ms 36696 KB n=2000
70 Correct 8 ms 36696 KB n=2000
71 Correct 9 ms 36700 KB n=2000
72 Correct 9 ms 36952 KB n=2000
73 Correct 9 ms 36696 KB n=2000
74 Correct 10 ms 36444 KB n=1844
75 Correct 11 ms 36696 KB n=2000
76 Correct 11 ms 36700 KB n=2000
77 Correct 10 ms 36700 KB n=2000
78 Correct 9 ms 36700 KB n=2000
79 Correct 10 ms 36496 KB n=2000
80 Correct 9 ms 36640 KB n=2000
81 Correct 10 ms 36696 KB n=2000
82 Correct 10 ms 36696 KB n=2000
83 Correct 10 ms 36700 KB n=2000
84 Correct 10 ms 36668 KB n=2000
85 Correct 10 ms 36700 KB n=2000
86 Correct 10 ms 36700 KB n=2000
87 Correct 9 ms 36700 KB n=2000
88 Correct 8 ms 36696 KB n=2000
89 Correct 8 ms 36700 KB n=2000
90 Correct 10 ms 36700 KB n=2000
91 Correct 9 ms 36696 KB n=2000
92 Correct 2270 ms 78772 KB n=200000
93 Correct 1877 ms 82024 KB n=200000
94 Correct 1192 ms 84852 KB n=200000
95 Correct 2199 ms 78348 KB n=200000
96 Correct 2133 ms 78536 KB n=200000
97 Correct 2098 ms 81268 KB n=200000
98 Correct 2212 ms 78716 KB n=200000
99 Correct 2206 ms 78696 KB n=200000
100 Correct 2345 ms 78476 KB n=200000
101 Correct 964 ms 85548 KB n=200000
102 Correct 1004 ms 79696 KB n=200000
103 Correct 860 ms 79744 KB n=200000
104 Correct 877 ms 79744 KB n=200000
105 Correct 848 ms 80140 KB n=200000
106 Correct 842 ms 80120 KB n=200000
107 Correct 818 ms 80420 KB n=200000
108 Correct 2239 ms 78680 KB n=200000
109 Correct 2128 ms 78716 KB n=200000
110 Correct 2058 ms 78676 KB n=200000
111 Correct 1785 ms 77852 KB n=200000
112 Correct 1119 ms 85052 KB n=200000
113 Correct 2020 ms 80968 KB n=200000
114 Correct 1796 ms 77984 KB n=200000
115 Correct 2420 ms 78916 KB n=200000
116 Correct 2178 ms 78700 KB n=200000
117 Correct 1082 ms 85184 KB n=200000
118 Correct 2356 ms 79984 KB n=200000
119 Correct 2163 ms 78524 KB n=200000
120 Correct 778 ms 84524 KB n=200000
121 Correct 769 ms 84552 KB n=200000
122 Correct 907 ms 84968 KB n=200000
123 Correct 827 ms 80012 KB n=200000
124 Correct 190 ms 51604 KB n=25264