oj.uz

Submission #173253

# Submission time Handle Problem Language Result Execution time Memory
173253 2020-01-03T16:49:23 Z LinusTorvaldsFan Birthday gift (IZhO18_treearray) C++14
12 / 100
 4000 ms 5240 KB 
#include <bits/stdc++.h>

using namespace std;


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

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

void gfs(int v, int p){
	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});
	}
}

int lca(int x, int y) {
	if(min_tin[x]>min_tin[y]){
		swap(x,y);
	}
	pair<int,int> ans={h[x],x};
	for(int i=min_tin[x];i<=min_tin[y];i++){
		ans=min(ans,euler_path[i]);
	}
	return ans.second;
}

int main() {
	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);
	vector<int>a(m);
	for(int i=0;i<m;i++){
		cin>>a[i];
	}
	for(;q;q--){
		int t;
		cin>>t;
		if(t==1) {
			int pos,v;
			cin>>pos>>v;
			pos--;
			a[pos]=v;
		}
		if(t==2) {
			int l,r,v;
			cin>>l>>r>>v;
			l--;r--;
			int ansL=-1;
			int ansR=-1;
			for(int i=l;i<=r;i++){
				int cur_lca=a[i];
				for(int j=i;j<=r;j++){
					cur_lca=lca(cur_lca,a[j]);
					if(cur_lca==v){
						ansL=i+1;
						ansR=j+1;	
						break;
					}
				}
			}
			cout<<ansL<<" "<<ansR<<"\n";
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 14 ms 5112 KB n=100
3 Correct 11 ms 5116 KB n=100
4 Correct 10 ms 5112 KB n=100
5 Correct 10 ms 5112 KB n=100
6 Correct 51 ms 4984 KB n=100
7 Correct 52 ms 5112 KB n=100
8 Correct 11 ms 4984 KB n=100
9 Correct 11 ms 4984 KB n=100
10 Correct 30 ms 5112 KB n=100
11 Correct 30 ms 4984 KB n=100
12 Correct 9 ms 5112 KB n=100
13 Correct 8 ms 4984 KB n=100
14 Correct 8 ms 5096 KB n=100
15 Correct 8 ms 4984 KB n=100
16 Correct 8 ms 5116 KB n=100
17 Correct 11 ms 5112 KB n=100
18 Correct 9 ms 5112 KB n=100
19 Correct 6 ms 4984 KB n=100
20 Correct 10 ms 5116 KB n=100
21 Correct 9 ms 5112 KB n=100
22 Correct 7 ms 5112 KB n=100
23 Correct 11 ms 4984 KB n=100
24 Correct 11 ms 5112 KB n=100
25 Correct 11 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 23 ms 4988 KB n=100
28 Correct 170 ms 5140 KB n=500
29 Correct 1386 ms 5160 KB n=500
30 Correct 1454 ms 5240 KB n=500
31 Correct 1453 ms 5112 KB n=500
32 Correct 514 ms 5112 KB n=500
33 Correct 1720 ms 5180 KB n=500
34 Correct 68 ms 5112 KB n=500
35 Correct 1275 ms 5112 KB n=500
36 Execution timed out 4096 ms 5112 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 14 ms 5112 KB n=100
3 Correct 11 ms 5116 KB n=100
4 Correct 10 ms 5112 KB n=100
5 Correct 10 ms 5112 KB n=100
6 Correct 51 ms 4984 KB n=100
7 Correct 52 ms 5112 KB n=100
8 Correct 11 ms 4984 KB n=100
9 Correct 11 ms 4984 KB n=100
10 Correct 30 ms 5112 KB n=100
11 Correct 30 ms 4984 KB n=100
12 Correct 9 ms 5112 KB n=100
13 Correct 8 ms 4984 KB n=100
14 Correct 8 ms 5096 KB n=100
15 Correct 8 ms 4984 KB n=100
16 Correct 8 ms 5116 KB n=100
17 Correct 11 ms 5112 KB n=100
18 Correct 9 ms 5112 KB n=100
19 Correct 6 ms 4984 KB n=100
20 Correct 10 ms 5116 KB n=100
21 Correct 9 ms 5112 KB n=100
22 Correct 7 ms 5112 KB n=100
23 Correct 11 ms 4984 KB n=100
24 Correct 11 ms 5112 KB n=100
25 Correct 11 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 23 ms 4988 KB n=100
28 Correct 170 ms 5140 KB n=500
29 Correct 1386 ms 5160 KB n=500
30 Correct 1454 ms 5240 KB n=500
31 Correct 1453 ms 5112 KB n=500
32 Correct 514 ms 5112 KB n=500
33 Correct 1720 ms 5180 KB n=500
34 Correct 68 ms 5112 KB n=500
35 Correct 1275 ms 5112 KB n=500
36 Execution timed out 4096 ms 5112 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 14 ms 5112 KB n=100
3 Correct 11 ms 5116 KB n=100
4 Correct 10 ms 5112 KB n=100
5 Correct 10 ms 5112 KB n=100
6 Correct 51 ms 4984 KB n=100
7 Correct 52 ms 5112 KB n=100
8 Correct 11 ms 4984 KB n=100
9 Correct 11 ms 4984 KB n=100
10 Correct 30 ms 5112 KB n=100
11 Correct 30 ms 4984 KB n=100
12 Correct 9 ms 5112 KB n=100
13 Correct 8 ms 4984 KB n=100
14 Correct 8 ms 5096 KB n=100
15 Correct 8 ms 4984 KB n=100
16 Correct 8 ms 5116 KB n=100
17 Correct 11 ms 5112 KB n=100
18 Correct 9 ms 5112 KB n=100
19 Correct 6 ms 4984 KB n=100
20 Correct 10 ms 5116 KB n=100
21 Correct 9 ms 5112 KB n=100
22 Correct 7 ms 5112 KB n=100
23 Correct 11 ms 4984 KB n=100
24 Correct 11 ms 5112 KB n=100
25 Correct 11 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 23 ms 4988 KB n=100
28 Correct 170 ms 5140 KB n=500
29 Correct 1386 ms 5160 KB n=500
30 Correct 1454 ms 5240 KB n=500
31 Correct 1453 ms 5112 KB n=500
32 Correct 514 ms 5112 KB n=500
33 Correct 1720 ms 5180 KB n=500
34 Correct 68 ms 5112 KB n=500
35 Correct 1275 ms 5112 KB n=500
36 Execution timed out 4096 ms 5112 KB Time limit exceeded
37 Halted 0 ms 0 KB -