oj.uz

Submission #173267

# Submission time Handle Problem Language Result Execution time Memory
173267 2020-01-03T17:13:49 Z LinusTorvaldsFan Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 28680 KB 
#include <bits/stdc++.h>

using namespace std;


const int maxn=2e5+19;
vector<int>T[maxn];

int tin[maxn];
int tout[maxn];
int timer=0;

vector<pair<int,int>>euler_path;
int min_tin[maxn];
int h[maxn];

void gfs(int v, int p){
	tin[v]=++timer;
	min_tin[v]=euler_path.size();
	euler_path.push_back({h[v],v});
	for(auto u:T[v]){
		if(u==p)continue;
		h[u]=h[v]+1;
		gfs(u,v);
		euler_path.push_back({h[v],v});
	}
	tout[v]=++timer;
}

const int Q=1<<18;
pair<int,int>tree[2*Q];
int lca_tree[2*Q];

const int inf=1e9;

void update(int p, pair<int,int>x) {
	p+=Q;
	tree[p]=x;
	p/=2;
	while(p>0){
		tree[p]=min(tree[p*2],tree[2*p+1]);
		p/=2;
	}
}

pair<int,int> get(int l, int r) {
	pair<int,int> ans={inf,inf};
	for(l+=Q,r+=Q;l<r;l>>=1,r>>=1){
		if(l&1)ans=min(ans,tree[l++]);
		if(r&1)ans=min(ans,tree[--r]);
	}
	return ans;
}

int lca(int x, int y);

void update_lca_tree(int p, int x) {
	p+=Q;
	lca_tree[p]=x;
	p/=2;
	while(p>0){
		lca_tree[p]=lca(lca_tree[2*p],lca_tree[2*p+1]);
		p/=2;
	}
}

int get_lca(int l, int r) {
	int ans=-1;
	for(l+=Q,r+=Q;l<r;l/=2,r/=2){
		if(l&1) ans=lca(ans,lca_tree[l++]);
		if(r&1) ans=lca(ans,lca_tree[--r]);
	}
	return ans;
}

int lca(int x, int y) {
	if(x==-1)return y;
	if(min_tin[x]>min_tin[y]){
		swap(x,y);
	}
	pair<int,int> ans=get(min_tin[x],min_tin[y]+1);
	return ans.second;
}

bool check_subtree(int root, int child) {
	return tin[root] <= tin[child] && tout[child]<=tout[root];
}

int main() {
	fill(tree,tree+2*Q,make_pair(inf,inf));
	memset(lca_tree,255,sizeof(lca_tree));
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	int m;
	cin>>m;
	int q;
	cin>>q;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		T[a].push_back(b);
		T[b].push_back(a);	
	}
	gfs(1,-1);
	for(int i=0;i<(int)euler_path.size();i++){
		update(i,euler_path[i]);
	}
	
	vector<int>a(m);
	for(int i=0;i<m;i++){
		cin>>a[i];
		update_lca_tree(i,a[i]);
	}
	for(;q;q--){
		int t;
		cin>>t;
		if(t==1) {
			int pos,v;
			cin>>pos>>v;
			pos--;
			a[pos]=v;
			update_lca_tree(pos,v);
		}
		if(t==2) {
			int l,r,v;
			cin>>l>>r>>v;
			l--;r--;
			int ansL=-1;
			int ansR=-1;
			
			int check=get_lca(l,r+1);
			if(!check_subtree(check,v)) {
				cout<<"-1 -1\n";
				continue;
			}
			for(int i=l;i<=r;i++){
				int L=i-1;
				int R=r;
				while(R-L>1){
					int M=(L+R)/2;
					int now=get_lca(i,M+1);
					if(check_subtree(now,v)){
						R=M;
					}else{
						L=M;
					}
				}
				int now=get_lca(i,R+1);
				if(now==v){
					ansL=i+1;
					ansR=R+1;
					break;
				}
			}
			cout<<ansL<<" "<<ansR<<"\n";
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB n=5
2 Correct 12 ms 11256 KB n=100
3 Correct 12 ms 11256 KB n=100
4 Correct 12 ms 11256 KB n=100
5 Correct 12 ms 11256 KB n=100
6 Correct 14 ms 11248 KB n=100
7 Correct 14 ms 11256 KB n=100
8 Correct 13 ms 11256 KB n=100
9 Correct 13 ms 11256 KB n=100
10 Correct 13 ms 11256 KB n=100
11 Correct 13 ms 11256 KB n=100
12 Correct 11 ms 11256 KB n=100
13 Correct 12 ms 11296 KB n=100
14 Correct 12 ms 11228 KB n=100
15 Correct 12 ms 11256 KB n=100
16 Correct 12 ms 11256 KB n=100
17 Correct 15 ms 11384 KB n=100
18 Correct 12 ms 11256 KB n=100
19 Correct 12 ms 11128 KB n=100
20 Correct 12 ms 11256 KB n=100
21 Correct 12 ms 11228 KB n=100
22 Correct 11 ms 11256 KB n=100
23 Correct 12 ms 11284 KB n=100
24 Correct 12 ms 11256 KB n=100
25 Correct 12 ms 11256 KB n=100
26 Correct 11 ms 11256 KB n=12
27 Correct 13 ms 11256 KB n=100
28 Correct 13 ms 11256 KB n=500
29 Correct 46 ms 11256 KB n=500
30 Correct 41 ms 11256 KB n=500
31 Correct 43 ms 11436 KB n=500
32 Correct 13 ms 11228 KB n=500
33 Correct 38 ms 11256 KB n=500
34 Correct 12 ms 11224 KB n=500
35 Correct 43 ms 11256 KB n=500
36 Correct 157 ms 11324 KB n=500
37 Correct 157 ms 11388 KB n=500
38 Correct 154 ms 11324 KB n=500
39 Correct 56 ms 11256 KB n=500
40 Correct 54 ms 11256 KB n=500
41 Correct 53 ms 11256 KB n=500
42 Correct 92 ms 11384 KB n=500
43 Correct 93 ms 11384 KB n=500
44 Correct 89 ms 11256 KB n=500
45 Correct 12 ms 11256 KB n=500
46 Correct 46 ms 11320 KB n=500
47 Correct 40 ms 11260 KB n=500
48 Correct 13 ms 11256 KB n=500
49 Correct 38 ms 11316 KB n=500
50 Correct 37 ms 11256 KB n=500
51 Correct 59 ms 11256 KB n=500
52 Correct 72 ms 11384 KB n=500
53 Correct 61 ms 11256 KB n=500
54 Correct 13 ms 11256 KB n=500
55 Correct 18 ms 11256 KB n=278
56 Correct 12 ms 11256 KB n=500
57 Correct 13 ms 11256 KB n=500
58 Correct 113 ms 11256 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB n=5
2 Correct 12 ms 11256 KB n=100
3 Correct 12 ms 11256 KB n=100
4 Correct 12 ms 11256 KB n=100
5 Correct 12 ms 11256 KB n=100
6 Correct 14 ms 11248 KB n=100
7 Correct 14 ms 11256 KB n=100
8 Correct 13 ms 11256 KB n=100
9 Correct 13 ms 11256 KB n=100
10 Correct 13 ms 11256 KB n=100
11 Correct 13 ms 11256 KB n=100
12 Correct 11 ms 11256 KB n=100
13 Correct 12 ms 11296 KB n=100
14 Correct 12 ms 11228 KB n=100
15 Correct 12 ms 11256 KB n=100
16 Correct 12 ms 11256 KB n=100
17 Correct 15 ms 11384 KB n=100
18 Correct 12 ms 11256 KB n=100
19 Correct 12 ms 11128 KB n=100
20 Correct 12 ms 11256 KB n=100
21 Correct 12 ms 11228 KB n=100
22 Correct 11 ms 11256 KB n=100
23 Correct 12 ms 11284 KB n=100
24 Correct 12 ms 11256 KB n=100
25 Correct 12 ms 11256 KB n=100
26 Correct 11 ms 11256 KB n=12
27 Correct 13 ms 11256 KB n=100
28 Correct 13 ms 11256 KB n=500
29 Correct 46 ms 11256 KB n=500
30 Correct 41 ms 11256 KB n=500
31 Correct 43 ms 11436 KB n=500
32 Correct 13 ms 11228 KB n=500
33 Correct 38 ms 11256 KB n=500
34 Correct 12 ms 11224 KB n=500
35 Correct 43 ms 11256 KB n=500
36 Correct 157 ms 11324 KB n=500
37 Correct 157 ms 11388 KB n=500
38 Correct 154 ms 11324 KB n=500
39 Correct 56 ms 11256 KB n=500
40 Correct 54 ms 11256 KB n=500
41 Correct 53 ms 11256 KB n=500
42 Correct 92 ms 11384 KB n=500
43 Correct 93 ms 11384 KB n=500
44 Correct 89 ms 11256 KB n=500
45 Correct 12 ms 11256 KB n=500
46 Correct 46 ms 11320 KB n=500
47 Correct 40 ms 11260 KB n=500
48 Correct 13 ms 11256 KB n=500
49 Correct 38 ms 11316 KB n=500
50 Correct 37 ms 11256 KB n=500
51 Correct 59 ms 11256 KB n=500
52 Correct 72 ms 11384 KB n=500
53 Correct 61 ms 11256 KB n=500
54 Correct 13 ms 11256 KB n=500
55 Correct 18 ms 11256 KB n=278
56 Correct 12 ms 11256 KB n=500
57 Correct 13 ms 11256 KB n=500
58 Correct 113 ms 11256 KB n=500
59 Correct 20 ms 11384 KB n=2000
60 Correct 932 ms 11640 KB n=2000
61 Correct 874 ms 11640 KB n=2000
62 Correct 602 ms 11512 KB n=2000
63 Correct 24 ms 11384 KB n=2000
64 Correct 799 ms 11612 KB n=2000
65 Correct 17 ms 11384 KB n=2000
66 Correct 1010 ms 11612 KB n=2000
67 Correct 44 ms 11384 KB n=2000
68 Correct 831 ms 11532 KB n=2000
69 Correct 3557 ms 11620 KB n=2000
70 Correct 3554 ms 11592 KB n=2000
71 Correct 3563 ms 11544 KB n=2000
72 Correct 1183 ms 11516 KB n=2000
73 Correct 1187 ms 11604 KB n=2000
74 Correct 17 ms 11384 KB n=1844
75 Correct 1212 ms 11516 KB n=2000
76 Correct 1972 ms 11732 KB n=2000
77 Correct 1969 ms 11592 KB n=2000
78 Correct 2072 ms 11604 KB n=2000
79 Correct 17 ms 11388 KB n=2000
80 Correct 800 ms 11564 KB n=2000
81 Correct 726 ms 11520 KB n=2000
82 Correct 17 ms 11384 KB n=2000
83 Correct 790 ms 11640 KB n=2000
84 Correct 744 ms 11512 KB n=2000
85 Correct 1346 ms 11512 KB n=2000
86 Correct 1438 ms 11628 KB n=2000
87 Correct 816 ms 11516 KB n=2000
88 Correct 16 ms 11512 KB n=2000
89 Correct 16 ms 11512 KB n=2000
90 Correct 17 ms 11512 KB n=2000
91 Correct 2641 ms 11484 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11256 KB n=5
2 Correct 12 ms 11256 KB n=100
3 Correct 12 ms 11256 KB n=100
4 Correct 12 ms 11256 KB n=100
5 Correct 12 ms 11256 KB n=100
6 Correct 14 ms 11248 KB n=100
7 Correct 14 ms 11256 KB n=100
8 Correct 13 ms 11256 KB n=100
9 Correct 13 ms 11256 KB n=100
10 Correct 13 ms 11256 KB n=100
11 Correct 13 ms 11256 KB n=100
12 Correct 11 ms 11256 KB n=100
13 Correct 12 ms 11296 KB n=100
14 Correct 12 ms 11228 KB n=100
15 Correct 12 ms 11256 KB n=100
16 Correct 12 ms 11256 KB n=100
17 Correct 15 ms 11384 KB n=100
18 Correct 12 ms 11256 KB n=100
19 Correct 12 ms 11128 KB n=100
20 Correct 12 ms 11256 KB n=100
21 Correct 12 ms 11228 KB n=100
22 Correct 11 ms 11256 KB n=100
23 Correct 12 ms 11284 KB n=100
24 Correct 12 ms 11256 KB n=100
25 Correct 12 ms 11256 KB n=100
26 Correct 11 ms 11256 KB n=12
27 Correct 13 ms 11256 KB n=100
28 Correct 13 ms 11256 KB n=500
29 Correct 46 ms 11256 KB n=500
30 Correct 41 ms 11256 KB n=500
31 Correct 43 ms 11436 KB n=500
32 Correct 13 ms 11228 KB n=500
33 Correct 38 ms 11256 KB n=500
34 Correct 12 ms 11224 KB n=500
35 Correct 43 ms 11256 KB n=500
36 Correct 157 ms 11324 KB n=500
37 Correct 157 ms 11388 KB n=500
38 Correct 154 ms 11324 KB n=500
39 Correct 56 ms 11256 KB n=500
40 Correct 54 ms 11256 KB n=500
41 Correct 53 ms 11256 KB n=500
42 Correct 92 ms 11384 KB n=500
43 Correct 93 ms 11384 KB n=500
44 Correct 89 ms 11256 KB n=500
45 Correct 12 ms 11256 KB n=500
46 Correct 46 ms 11320 KB n=500
47 Correct 40 ms 11260 KB n=500
48 Correct 13 ms 11256 KB n=500
49 Correct 38 ms 11316 KB n=500
50 Correct 37 ms 11256 KB n=500
51 Correct 59 ms 11256 KB n=500
52 Correct 72 ms 11384 KB n=500
53 Correct 61 ms 11256 KB n=500
54 Correct 13 ms 11256 KB n=500
55 Correct 18 ms 11256 KB n=278
56 Correct 12 ms 11256 KB n=500
57 Correct 13 ms 11256 KB n=500
58 Correct 113 ms 11256 KB n=500
59 Correct 20 ms 11384 KB n=2000
60 Correct 932 ms 11640 KB n=2000
61 Correct 874 ms 11640 KB n=2000
62 Correct 602 ms 11512 KB n=2000
63 Correct 24 ms 11384 KB n=2000
64 Correct 799 ms 11612 KB n=2000
65 Correct 17 ms 11384 KB n=2000
66 Correct 1010 ms 11612 KB n=2000
67 Correct 44 ms 11384 KB n=2000
68 Correct 831 ms 11532 KB n=2000
69 Correct 3557 ms 11620 KB n=2000
70 Correct 3554 ms 11592 KB n=2000
71 Correct 3563 ms 11544 KB n=2000
72 Correct 1183 ms 11516 KB n=2000
73 Correct 1187 ms 11604 KB n=2000
74 Correct 17 ms 11384 KB n=1844
75 Correct 1212 ms 11516 KB n=2000
76 Correct 1972 ms 11732 KB n=2000
77 Correct 1969 ms 11592 KB n=2000
78 Correct 2072 ms 11604 KB n=2000
79 Correct 17 ms 11388 KB n=2000
80 Correct 800 ms 11564 KB n=2000
81 Correct 726 ms 11520 KB n=2000
82 Correct 17 ms 11384 KB n=2000
83 Correct 790 ms 11640 KB n=2000
84 Correct 744 ms 11512 KB n=2000
85 Correct 1346 ms 11512 KB n=2000
86 Correct 1438 ms 11628 KB n=2000
87 Correct 816 ms 11516 KB n=2000
88 Correct 16 ms 11512 KB n=2000
89 Correct 16 ms 11512 KB n=2000
90 Correct 17 ms 11512 KB n=2000
91 Correct 2641 ms 11484 KB n=2000
92 Execution timed out 4065 ms 28680 KB Time limit exceeded
93 Halted 0 ms 0 KB -