oj.uz

Submission #385514

# Submission time Handle Problem Language Result Execution time Memory
385514 2021-04-04T14:13:10 Z vanic Birthday gift (IZhO18_treearray) C++14
100 / 100
 1759 ms 63852 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int maxn=2e5+5, Log=18;

int n, m, q;
vector < int > ms[maxn];
int parent[maxn][Log];
int dep[maxn];

void dfs(int x, int prosl, int d){
	parent[x][0]=prosl;
	dep[x]=d;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs(ms[x][i], x, d+1);
		}
	}
}

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=0; j<n; j++){
			parent[j][i]=parent[parent[j][i-1]][i-1];
		}
	}
}

void digni(int &a, int &b){
	int raz=dep[a]-dep[b];
	for(int i=0; i<Log; i++){
		if((1<<i)&raz){
			a=parent[a][i];
		}
	}
}

int lca(int a, int b){
	if(dep[a]<dep[b]){
		swap(a, b);
	}
	digni(a, b);
	if(a==b){
		return a;
	}
	for(int i=Log-1; i>-1; i--){
		if(parent[a][i]!=parent[b][i]){
			a=parent[a][i];
			b=parent[b][i];
		}
	}
	return parent[a][0];
}

int l[maxn];
set < pair < int, int > > s;
set < pair < int, int > > s1;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	int a, b;
	for(int i=0; i<n-1; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	dfs(0, 0, 0);
	precompute();
	for(int i=0; i<m; i++){
		cin >> l[i];
		l[i]--;
		s1.insert({l[i], i});
		if(i){
			s.insert({lca(l[i-1], l[i]), i-1});
		}
	}
	int c, d;
	set < pair < int, int > >::iterator it;
	for(int i=0; i<q; i++){
		cin >> a;
		if(a==1){
			cin >> b >> c;
			b--;
			c--;
			s1.erase({l[b], b});
			s1.insert({c, b});
			if(b){
				s.erase({lca(l[b-1], l[b]), b-1});
				s.insert({lca(l[b-1], c), b-1});
			}
			if(b!=m-1){
				s.erase({lca(l[b], l[b+1]), b});
				s.insert({lca(c, l[b+1]), b});
			}
			l[b]=c;
		}
		else{
			cin >> b >> c >> d;
			d--;
			b--;
			c--;
			it=s.lower_bound({d, b});
			if(it!=s.end() && it->first==d && it->second<c){
				cout << it->second+1 << ' ' << it->second+2 << '\n';
			}
			else{
				it=s1.lower_bound({d, b});
				if(it!=s1.end() && it->first==d && it->second<=c){
					cout << it->second+1 << ' ' <<  it->second+1 << '\n';
				}
				else{
					cout << -1 << ' ' << -1 << '\n';
				}
			}
		}
		
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 4 ms 5100 KB n=100
4 Correct 4 ms 5100 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 5 ms 5100 KB n=100
7 Correct 4 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 4 ms 5100 KB n=100
11 Correct 4 ms 5100 KB n=100
12 Correct 4 ms 5100 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 5 ms 5100 KB n=100
15 Correct 6 ms 5100 KB n=100
16 Correct 5 ms 5100 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5100 KB n=100
19 Correct 4 ms 5100 KB n=100
20 Correct 4 ms 5100 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 5 ms 5100 KB n=100
24 Correct 7 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 4 ms 5100 KB n=12
27 Correct 4 ms 5100 KB n=100
28 Correct 5 ms 5228 KB n=500
29 Correct 6 ms 5228 KB n=500
30 Correct 5 ms 5228 KB n=500
31 Correct 5 ms 5228 KB n=500
32 Correct 5 ms 5100 KB n=500
33 Correct 5 ms 5228 KB n=500
34 Correct 5 ms 5228 KB n=500
35 Correct 6 ms 5228 KB n=500
36 Correct 6 ms 5228 KB n=500
37 Correct 5 ms 5228 KB n=500
38 Correct 5 ms 5228 KB n=500
39 Correct 5 ms 5228 KB n=500
40 Correct 5 ms 5228 KB n=500
41 Correct 5 ms 5228 KB n=500
42 Correct 5 ms 5100 KB n=500
43 Correct 5 ms 5120 KB n=500
44 Correct 5 ms 5100 KB n=500
45 Correct 5 ms 5228 KB n=500
46 Correct 5 ms 5228 KB n=500
47 Correct 5 ms 5228 KB n=500
48 Correct 5 ms 5228 KB n=500
49 Correct 5 ms 5228 KB n=500
50 Correct 5 ms 5228 KB n=500
51 Correct 6 ms 5228 KB n=500
52 Correct 5 ms 5228 KB n=500
53 Correct 5 ms 5248 KB n=500
54 Correct 6 ms 5228 KB n=500
55 Correct 5 ms 5100 KB n=278
56 Correct 5 ms 5356 KB n=500
57 Correct 5 ms 5228 KB n=500
58 Correct 5 ms 5228 KB n=500
59 Correct 8 ms 5612 KB n=2000
60 Correct 9 ms 5740 KB n=2000
61 Correct 10 ms 5612 KB n=2000
62 Correct 9 ms 5612 KB n=2000
63 Correct 8 ms 5612 KB n=2000
64 Correct 10 ms 5612 KB n=2000
65 Correct 8 ms 5612 KB n=2000
66 Correct 9 ms 5612 KB n=2000
67 Correct 11 ms 5484 KB n=2000
68 Correct 10 ms 5740 KB n=2000
69 Correct 7 ms 5612 KB n=2000
70 Correct 7 ms 5612 KB n=2000
71 Correct 7 ms 5612 KB n=2000
72 Correct 7 ms 5612 KB n=2000
73 Correct 7 ms 5612 KB n=2000
74 Correct 8 ms 5484 KB n=1844
75 Correct 7 ms 5612 KB n=2000
76 Correct 9 ms 5612 KB n=2000
77 Correct 9 ms 5520 KB n=2000
78 Correct 8 ms 5484 KB n=2000
79 Correct 10 ms 5484 KB n=2000
80 Correct 9 ms 5612 KB n=2000
81 Correct 9 ms 5740 KB n=2000
82 Correct 9 ms 5612 KB n=2000
83 Correct 9 ms 5612 KB n=2000
84 Correct 8 ms 5612 KB n=2000
85 Correct 9 ms 5612 KB n=2000
86 Correct 9 ms 5612 KB n=2000
87 Correct 8 ms 5612 KB n=2000
88 Correct 9 ms 5612 KB n=2000
89 Correct 9 ms 5612 KB n=2000
90 Correct 9 ms 5612 KB n=2000
91 Correct 9 ms 5612 KB n=2000
92 Correct 1143 ms 54340 KB n=200000
93 Correct 1759 ms 59320 KB n=200000
94 Correct 1740 ms 62612 KB n=200000
95 Correct 1093 ms 54124 KB n=200000
96 Correct 1119 ms 54088 KB n=200000
97 Correct 1733 ms 58212 KB n=200000
98 Correct 1128 ms 54196 KB n=200000
99 Correct 1401 ms 54380 KB n=200000
100 Correct 1142 ms 54292 KB n=200000
101 Correct 1696 ms 63852 KB n=200000
102 Correct 624 ms 55252 KB n=200000
103 Correct 623 ms 55276 KB n=200000
104 Correct 621 ms 55276 KB n=200000
105 Correct 630 ms 55660 KB n=200000
106 Correct 620 ms 55776 KB n=200000
107 Correct 625 ms 55772 KB n=200000
108 Correct 1225 ms 54380 KB n=200000
109 Correct 1229 ms 54252 KB n=200000
110 Correct 1227 ms 54200 KB n=200000
111 Correct 1114 ms 53668 KB n=200000
112 Correct 1687 ms 62824 KB n=200000
113 Correct 1703 ms 58352 KB n=200000
114 Correct 1048 ms 53640 KB n=200000
115 Correct 1706 ms 56252 KB n=200000
116 Correct 1080 ms 54380 KB n=200000
117 Correct 1715 ms 63200 KB n=200000
118 Correct 1726 ms 57156 KB n=200000
119 Correct 1082 ms 54280 KB n=200000
120 Correct 1593 ms 62748 KB n=200000
121 Correct 1583 ms 62768 KB n=200000
122 Correct 1600 ms 63096 KB n=200000
123 Correct 656 ms 55492 KB n=200000
124 Correct 353 ms 19820 KB n=25264