oj.uz

답안 #909643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
909643 2024-01-17T10:09:27 Z daoquanglinh2007 Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 96180 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
 
const int NM = 2e5, LOG = 18, BL = 100;
 
int n, m, q;
vector <int> adj[NM+5];
int dep[NM+5], timer = 0, tin[NM+5], tout[NM+5];
pii f[LOG+5][2*NM+5];
int lg[2*NM+5];
int a[NM+5], g[NM/BL+5];
int pref[NM+5], suff[NM+5];
vector <int> arr[NM/BL+5];
vector <int> st;
 
void dfs(int u, int p){
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	tin[u] = ++timer;
	f[0][timer] = mp(dep[u], u);
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		f[0][++timer] = mp(dep[u], u);
	}
	tout[u] = timer;
}
 
void build_sparse(){
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= timer; j++)
			f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
			
	lg[1] = 0;
	for (int i = 2; i <= timer; i++)
		lg[i] = lg[i>>1]+1;
}
 
int lca(int u, int v){
	int l = tin[u], r = tin[v];
	if (l > r) swap(l, r);
	int k = __lg(r-l+1);
	return min(f[k][l], f[k][r-(1<<k)+1]).se;
}
 
bool is_ancestor(int a, int u){
	return tin[a] <= tin[u] && tout[a] >= tout[u];
}
 
void build(int id){
	arr[id].clear();
	st.clear();
	for (int i = id*BL; i < min((id+1)*BL, m); i++){
		if (st.empty()){
			st.push_back(a[i]);
			arr[id].push_back(a[i]);
			continue;
		}
		int tmp = lca(a[i], st.back());
		while (!st.empty() && is_ancestor(tmp, st.back())) st.pop_back();
		st.push_back(tmp);
		arr[id].push_back(tmp);
		if (tmp != a[i]){
			st.push_back(a[i]);
			arr[id].push_back(a[i]);
		}
	}
	sort(arr[id].begin(), arr[id].end());
	arr[id].erase(unique(arr[id].begin(), arr[id].end()), arr[id].end());
	
	pref[id*BL] = a[id*BL];
	for (int i = id*BL+1; i < min((id+1)*BL, m); i++)
		pref[i] = lca(pref[i-1], a[i]);
	suff[min((id+1)*BL, m)-1] = a[min((id+1)*BL, m)-1];
	for (int i = min((id+1)*BL, m)-2; i >= id*BL; i--)
		suff[i] = lca(suff[i+1], a[i]);
	g[id] = suff[id*BL];
}
 
void preprocess(){
	for (int i = 0; i*BL < m; i++){
		build(i);
	}
}
 
void update(int x, int val){
	a[x] = val;
	build(x/BL);
}
 
pii manual_query(int l, int r, int v){
	for (int i = l; i <= r; i++)
		if (is_ancestor(v, a[i])){
			int cur = a[i], j = i;
			while (j < r){
				int ne = lca(cur, a[j+1]);
				if (is_ancestor(v, ne)){
					cur = ne;
					j++;
				}
				else break;
			}
			if (cur == v) return mp(i, j);
			i = j+1;
		}
	return mp(-1, -1);
}
 
pii query(int l, int r, int v){
	int L = (l+BL-1)/BL, R = (r-BL+1)/BL;
	if (l/BL == r/BL || L > R){
		return manual_query(l, r, v);
	}
	for (int i = L; i <= R; i++)
		if (arr[i].back() >= v && arr[i][lower_bound(arr[i].begin(), arr[i].end(), v)-arr[i].begin()] == v){
			return manual_query(i*BL, min((i+1)*BL, m)-1, v);
		}
	pii tmp = manual_query(l, L*BL-1, v);
	if (tmp.fi != -1) return tmp;
	tmp = manual_query((R+1)*BL, r, v);
	if (tmp.fi != -1) return tmp;
	
	for (int i = L; i <= R+1; i++)
		if (i <= R && is_ancestor(v, g[i])){
			int j = i, cur = g[i];
			while (j < R){
				int ne = lca(cur, g[j+1]);
				if (is_ancestor(v, ne)){
					cur = ne;
					j++;
				}
				else break;
			}
			if (cur == v){
				return mp(i*BL, min((j+1)*BL, m)-1);
			}
			int lo = max(l, (i-1)*BL), hi = i*BL-1, resl = i*BL;
			if (lo <= hi && is_ancestor(v, a[hi])){
				while (lo <= hi){
					int mid = (lo+hi)/2;
					if (is_ancestor(v, suff[mid])){
						resl = mid;
						hi = mid-1;
					}
					else lo = mid+1;
				}
			}
			if (resl < i*BL) cur = lca(cur, suff[resl]);
			
			lo = (j+1)*BL, hi = min(r, (j+2)*BL-1);
			int resr = (j+1)*BL-1;
			if (lo <= hi && is_ancestor(v, a[lo])){
				while (lo <= hi){
					int mid = (lo+hi)/2;
					if (is_ancestor(v, pref[mid])){
						resr = mid;
						lo = mid+1;
					}
					else hi = mid-1;
				}
			}
			if (resr >= (j+1)*BL) cur = lca(cur, pref[resr]);
			
			if (cur == v) return mp(resl, resr);
			
			i = j;
		}
		else{
			int lo = max(l, (i-1)*BL), hi = min(r, i*BL-1), resl = -1;
			if (lo <= hi && is_ancestor(v, a[hi])){
				while (lo <= hi){
					int mid = (lo+hi)/2;
					if (is_ancestor(v, suff[mid])){
						resl = mid;
						hi = mid-1;
					}
					else lo = mid+1;
				}
			}
			if (resl == -1) continue;
			lo = max(l, i*BL), hi = min(r, (i+1)*BL-1); int resr = -1;
			if (lo <= hi && is_ancestor(v, a[lo])){
				while (lo <= hi){
					int mid = (lo+hi)/2;
					if (is_ancestor(v, pref[mid])){
						resr = mid;
						lo = mid+1;
					}
					else hi = mid-1;
				}
			}
			if (resr == -1) continue;
			
			if (lca(suff[resl], pref[resr]) == v){
				return mp(resl, resr);
			}
		}
	return mp(-1, -1);
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, -1);
	build_sparse();
	
	for (int i = 0; i < m; i++) cin >> a[i];
	preprocess();
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, val; cin >> pos >> val;
			update(pos-1, val);
		}
		else{
			int l, r, v; cin >> l >> r >> v;
			pii ans = query(l-1, r-1, v);
			if (ans.fi != -1){
				int cur = a[ans.fi];
				for (int i = ans.fi+1; i <= ans.se; i++) cur = lca(cur, a[i]);
				ans.fi++, ans.se++;
			}
			cout << ans.fi << ' ' << ans.se << '\n';
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17500 KB n=5
2 Correct 5 ms 25780 KB n=100
3 Correct 7 ms 25692 KB n=100
4 Correct 6 ms 25692 KB n=100
5 Correct 6 ms 25692 KB n=100
6 Correct 6 ms 25692 KB n=100
7 Correct 5 ms 25692 KB n=100
8 Correct 5 ms 25692 KB n=100
9 Correct 6 ms 25692 KB n=100
10 Correct 6 ms 25692 KB n=100
11 Correct 7 ms 25692 KB n=100
12 Correct 6 ms 25688 KB n=100
13 Correct 7 ms 25688 KB n=100
14 Correct 6 ms 25692 KB n=100
15 Correct 5 ms 25692 KB n=100
16 Correct 6 ms 25688 KB n=100
17 Correct 6 ms 25692 KB n=100
18 Correct 6 ms 25692 KB n=100
19 Correct 6 ms 25924 KB n=100
20 Correct 6 ms 25932 KB n=100
21 Correct 7 ms 25880 KB n=100
22 Correct 6 ms 25692 KB n=100
23 Correct 6 ms 25688 KB n=100
24 Correct 5 ms 25908 KB n=100
25 Correct 6 ms 25692 KB n=100
26 Correct 4 ms 19548 KB n=12
27 Correct 6 ms 25692 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17500 KB n=5
2 Correct 5 ms 25780 KB n=100
3 Correct 7 ms 25692 KB n=100
4 Correct 6 ms 25692 KB n=100
5 Correct 6 ms 25692 KB n=100
6 Correct 6 ms 25692 KB n=100
7 Correct 5 ms 25692 KB n=100
8 Correct 5 ms 25692 KB n=100
9 Correct 6 ms 25692 KB n=100
10 Correct 6 ms 25692 KB n=100
11 Correct 7 ms 25692 KB n=100
12 Correct 6 ms 25688 KB n=100
13 Correct 7 ms 25688 KB n=100
14 Correct 6 ms 25692 KB n=100
15 Correct 5 ms 25692 KB n=100
16 Correct 6 ms 25688 KB n=100
17 Correct 6 ms 25692 KB n=100
18 Correct 6 ms 25692 KB n=100
19 Correct 6 ms 25924 KB n=100
20 Correct 6 ms 25932 KB n=100
21 Correct 7 ms 25880 KB n=100
22 Correct 6 ms 25692 KB n=100
23 Correct 6 ms 25688 KB n=100
24 Correct 5 ms 25908 KB n=100
25 Correct 6 ms 25692 KB n=100
26 Correct 4 ms 19548 KB n=12
27 Correct 6 ms 25692 KB n=100
28 Correct 8 ms 30044 KB n=500
29 Correct 9 ms 30044 KB n=500
30 Correct 9 ms 30044 KB n=500
31 Correct 8 ms 30044 KB n=500
32 Correct 8 ms 30040 KB n=500
33 Correct 10 ms 30040 KB n=500
34 Correct 9 ms 30040 KB n=500
35 Correct 8 ms 30044 KB n=500
36 Correct 7 ms 30044 KB n=500
37 Correct 8 ms 30040 KB n=500
38 Correct 6 ms 30044 KB n=500
39 Correct 6 ms 30044 KB n=500
40 Correct 7 ms 30044 KB n=500
41 Correct 7 ms 30044 KB n=500
42 Correct 8 ms 30296 KB n=500
43 Correct 9 ms 30044 KB n=500
44 Correct 9 ms 30044 KB n=500
45 Correct 9 ms 30044 KB n=500
46 Correct 9 ms 30056 KB n=500
47 Correct 8 ms 29876 KB n=500
48 Correct 8 ms 30044 KB n=500
49 Correct 8 ms 30044 KB n=500
50 Correct 8 ms 30040 KB n=500
51 Correct 9 ms 30044 KB n=500
52 Correct 8 ms 30044 KB n=500
53 Correct 8 ms 30040 KB n=500
54 Correct 8 ms 30044 KB n=500
55 Correct 7 ms 30040 KB n=278
56 Correct 8 ms 30044 KB n=500
57 Correct 8 ms 30044 KB n=500
58 Correct 6 ms 30040 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17500 KB n=5
2 Correct 5 ms 25780 KB n=100
3 Correct 7 ms 25692 KB n=100
4 Correct 6 ms 25692 KB n=100
5 Correct 6 ms 25692 KB n=100
6 Correct 6 ms 25692 KB n=100
7 Correct 5 ms 25692 KB n=100
8 Correct 5 ms 25692 KB n=100
9 Correct 6 ms 25692 KB n=100
10 Correct 6 ms 25692 KB n=100
11 Correct 7 ms 25692 KB n=100
12 Correct 6 ms 25688 KB n=100
13 Correct 7 ms 25688 KB n=100
14 Correct 6 ms 25692 KB n=100
15 Correct 5 ms 25692 KB n=100
16 Correct 6 ms 25688 KB n=100
17 Correct 6 ms 25692 KB n=100
18 Correct 6 ms 25692 KB n=100
19 Correct 6 ms 25924 KB n=100
20 Correct 6 ms 25932 KB n=100
21 Correct 7 ms 25880 KB n=100
22 Correct 6 ms 25692 KB n=100
23 Correct 6 ms 25688 KB n=100
24 Correct 5 ms 25908 KB n=100
25 Correct 6 ms 25692 KB n=100
26 Correct 4 ms 19548 KB n=12
27 Correct 6 ms 25692 KB n=100
28 Correct 8 ms 30044 KB n=500
29 Correct 9 ms 30044 KB n=500
30 Correct 9 ms 30044 KB n=500
31 Correct 8 ms 30044 KB n=500
32 Correct 8 ms 30040 KB n=500
33 Correct 10 ms 30040 KB n=500
34 Correct 9 ms 30040 KB n=500
35 Correct 8 ms 30044 KB n=500
36 Correct 7 ms 30044 KB n=500
37 Correct 8 ms 30040 KB n=500
38 Correct 6 ms 30044 KB n=500
39 Correct 6 ms 30044 KB n=500
40 Correct 7 ms 30044 KB n=500
41 Correct 7 ms 30044 KB n=500
42 Correct 8 ms 30296 KB n=500
43 Correct 9 ms 30044 KB n=500
44 Correct 9 ms 30044 KB n=500
45 Correct 9 ms 30044 KB n=500
46 Correct 9 ms 30056 KB n=500
47 Correct 8 ms 29876 KB n=500
48 Correct 8 ms 30044 KB n=500
49 Correct 8 ms 30044 KB n=500
50 Correct 8 ms 30040 KB n=500
51 Correct 9 ms 30044 KB n=500
52 Correct 8 ms 30044 KB n=500
53 Correct 8 ms 30040 KB n=500
54 Correct 8 ms 30044 KB n=500
55 Correct 7 ms 30040 KB n=278
56 Correct 8 ms 30044 KB n=500
57 Correct 8 ms 30044 KB n=500
58 Correct 6 ms 30040 KB n=500
59 Correct 16 ms 34256 KB n=2000
60 Correct 17 ms 34388 KB n=2000
61 Correct 17 ms 34140 KB n=2000
62 Correct 17 ms 34140 KB n=2000
63 Correct 16 ms 34136 KB n=2000
64 Correct 18 ms 34136 KB n=2000
65 Correct 15 ms 34256 KB n=2000
66 Correct 17 ms 34140 KB n=2000
67 Correct 18 ms 34136 KB n=2000
68 Correct 16 ms 34140 KB n=2000
69 Correct 9 ms 34140 KB n=2000
70 Correct 8 ms 34140 KB n=2000
71 Correct 9 ms 34140 KB n=2000
72 Correct 9 ms 34140 KB n=2000
73 Correct 9 ms 34140 KB n=2000
74 Correct 15 ms 34208 KB n=1844
75 Correct 10 ms 34140 KB n=2000
76 Correct 17 ms 34140 KB n=2000
77 Correct 18 ms 34140 KB n=2000
78 Correct 16 ms 34244 KB n=2000
79 Correct 15 ms 34136 KB n=2000
80 Correct 16 ms 34140 KB n=2000
81 Correct 19 ms 34516 KB n=2000
82 Correct 16 ms 34136 KB n=2000
83 Correct 18 ms 34140 KB n=2000
84 Correct 18 ms 34140 KB n=2000
85 Correct 17 ms 34136 KB n=2000
86 Correct 18 ms 34380 KB n=2000
87 Correct 17 ms 34140 KB n=2000
88 Correct 16 ms 34396 KB n=2000
89 Correct 16 ms 34396 KB n=2000
90 Correct 17 ms 34396 KB n=2000
91 Correct 8 ms 34140 KB n=2000

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17500 KB n=5
2 Correct 5 ms 25780 KB n=100
3 Correct 7 ms 25692 KB n=100
4 Correct 6 ms 25692 KB n=100
5 Correct 6 ms 25692 KB n=100
6 Correct 6 ms 25692 KB n=100
7 Correct 5 ms 25692 KB n=100
8 Correct 5 ms 25692 KB n=100
9 Correct 6 ms 25692 KB n=100
10 Correct 6 ms 25692 KB n=100
11 Correct 7 ms 25692 KB n=100
12 Correct 6 ms 25688 KB n=100
13 Correct 7 ms 25688 KB n=100
14 Correct 6 ms 25692 KB n=100
15 Correct 5 ms 25692 KB n=100
16 Correct 6 ms 25688 KB n=100
17 Correct 6 ms 25692 KB n=100
18 Correct 6 ms 25692 KB n=100
19 Correct 6 ms 25924 KB n=100
20 Correct 6 ms 25932 KB n=100
21 Correct 7 ms 25880 KB n=100
22 Correct 6 ms 25692 KB n=100
23 Correct 6 ms 25688 KB n=100
24 Correct 5 ms 25908 KB n=100
25 Correct 6 ms 25692 KB n=100
26 Correct 4 ms 19548 KB n=12
27 Correct 6 ms 25692 KB n=100
28 Correct 8 ms 30044 KB n=500
29 Correct 9 ms 30044 KB n=500
30 Correct 9 ms 30044 KB n=500
31 Correct 8 ms 30044 KB n=500
32 Correct 8 ms 30040 KB n=500
33 Correct 10 ms 30040 KB n=500
34 Correct 9 ms 30040 KB n=500
35 Correct 8 ms 30044 KB n=500
36 Correct 7 ms 30044 KB n=500
37 Correct 8 ms 30040 KB n=500
38 Correct 6 ms 30044 KB n=500
39 Correct 6 ms 30044 KB n=500
40 Correct 7 ms 30044 KB n=500
41 Correct 7 ms 30044 KB n=500
42 Correct 8 ms 30296 KB n=500
43 Correct 9 ms 30044 KB n=500
44 Correct 9 ms 30044 KB n=500
45 Correct 9 ms 30044 KB n=500
46 Correct 9 ms 30056 KB n=500
47 Correct 8 ms 29876 KB n=500
48 Correct 8 ms 30044 KB n=500
49 Correct 8 ms 30044 KB n=500
50 Correct 8 ms 30040 KB n=500
51 Correct 9 ms 30044 KB n=500
52 Correct 8 ms 30044 KB n=500
53 Correct 8 ms 30040 KB n=500
54 Correct 8 ms 30044 KB n=500
55 Correct 7 ms 30040 KB n=278
56 Correct 8 ms 30044 KB n=500
57 Correct 8 ms 30044 KB n=500
58 Correct 6 ms 30040 KB n=500
59 Correct 16 ms 34256 KB n=2000
60 Correct 17 ms 34388 KB n=2000
61 Correct 17 ms 34140 KB n=2000
62 Correct 17 ms 34140 KB n=2000
63 Correct 16 ms 34136 KB n=2000
64 Correct 18 ms 34136 KB n=2000
65 Correct 15 ms 34256 KB n=2000
66 Correct 17 ms 34140 KB n=2000
67 Correct 18 ms 34136 KB n=2000
68 Correct 16 ms 34140 KB n=2000
69 Correct 9 ms 34140 KB n=2000
70 Correct 8 ms 34140 KB n=2000
71 Correct 9 ms 34140 KB n=2000
72 Correct 9 ms 34140 KB n=2000
73 Correct 9 ms 34140 KB n=2000
74 Correct 15 ms 34208 KB n=1844
75 Correct 10 ms 34140 KB n=2000
76 Correct 17 ms 34140 KB n=2000
77 Correct 18 ms 34140 KB n=2000
78 Correct 16 ms 34244 KB n=2000
79 Correct 15 ms 34136 KB n=2000
80 Correct 16 ms 34140 KB n=2000
81 Correct 19 ms 34516 KB n=2000
82 Correct 16 ms 34136 KB n=2000
83 Correct 18 ms 34140 KB n=2000
84 Correct 18 ms 34140 KB n=2000
85 Correct 17 ms 34136 KB n=2000
86 Correct 18 ms 34380 KB n=2000
87 Correct 17 ms 34140 KB n=2000
88 Correct 16 ms 34396 KB n=2000
89 Correct 16 ms 34396 KB n=2000
90 Correct 17 ms 34396 KB n=2000
91 Correct 8 ms 34140 KB n=2000
92 Correct 1707 ms 81392 KB n=200000
93 Correct 3366 ms 88324 KB n=200000
94 Correct 3258 ms 93884 KB n=200000
95 Correct 1590 ms 81308 KB n=200000
96 Correct 1515 ms 81300 KB n=200000
97 Correct 3171 ms 87036 KB n=200000
98 Correct 1609 ms 81296 KB n=200000
99 Correct 1949 ms 80952 KB n=200000
100 Correct 1917 ms 81364 KB n=200000
101 Correct 3252 ms 96180 KB n=200000
102 Correct 2013 ms 82196 KB n=200000
103 Correct 1714 ms 82148 KB n=200000
104 Correct 1838 ms 82096 KB n=200000
105 Correct 395 ms 82012 KB n=200000
106 Correct 395 ms 82020 KB n=200000
107 Correct 439 ms 82228 KB n=200000
108 Correct 3077 ms 80768 KB n=200000
109 Correct 2482 ms 80752 KB n=200000
110 Correct 2433 ms 80968 KB n=200000
111 Correct 1414 ms 81008 KB n=200000
112 Correct 3212 ms 94344 KB n=200000
113 Correct 3098 ms 86748 KB n=200000
114 Correct 1454 ms 81352 KB n=200000
115 Correct 2796 ms 83300 KB n=200000
116 Execution timed out 4011 ms 80976 KB Time limit exceeded
117 Halted 0 ms 0 KB -