oj.uz

Submission #435542

# Submission time Handle Problem Language Result Execution time Memory
435542 2021-06-23T12:20:37 Z keta_tsimakuridze Birthday gift (IZhO18_treearray) C++14
100 / 100
 2016 ms 99596 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tmin[N],par[N][20],tmout[N],timer,n,m,q,a[N],Lg;
vector<int>V[N];
set<pair<int,int> >s[N];
void dfs(int u,int p) {
	tmin[u] = ++timer;
	par[u][0] = p;
	for(int i = 1;i<=Lg;i++) {
		par[u][i] = par[par[u][i-1]][i-1];
	}
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		dfs(V[u][i],u);
	}
	tmout[u] = timer;
}
bool check(int u,int v){
	if(tmin[u]<=tmin[v] && tmout[u]>=tmout[v]) return 1;
	return 0;
}
int find_lca(int u,int v){
	if(check(u,v)) return u;
	if(check(v,u)) return v;
	
	for(int i=Lg;i>=0;i--){
		if(par[u][i] && !check(par[u][i],v)) u = par[u][i];
	}

	return par[u][0];
}
 main(){
	cin>>n>>m>>q;
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	Lg = log2(n) + 1;
	dfs(1,0);
	for(int i=1;i<=m;i++) {
		cin >> a[i];
		if(i-1) {
			s[find_lca(a[i],a[i-1])].insert({i-1,i});
			
		}
		s[a[i]].insert({i,i});
	}
	while(q--) {
		cin>>t; 
		if(t==1) {
			int i,val;
			cin>>i>>val;
			s[a[i]].erase({i,i});
			if(i-1) {
				int lca = find_lca(a[i],a[i-1]);
				s[find_lca(a[i],a[i-1])].erase({i-1,i});
				s[find_lca(val,a[i-1])].insert({i-1,i});
				
			}
			if(i<m) {
				int lca = find_lca(a[i],a[i+1]);
				s[find_lca(a[i],a[i+1])].erase({i,i+1});
				s[find_lca(val,a[i+1])].insert({i,i+1});
			}	
			a[i] = val;
			s[a[i]].insert({i,i});
			
		}
		else {
			int u,l,r;
			cin>>l>>r>>u;
			if(!s[u].size() || s[u].upper_bound({l,0})==s[u].end() || (*s[u].upper_bound({l,0})).s>r) {
				cout<<"-1 -1"<<endl;
			}
			else cout<<(*s[u].upper_bound({l,0})).f<<" "<<(*s[u].upper_bound({l,0})).s<<endl;
		} 
	}
}

Compilation message

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:16:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
treearray.cpp: At global scope:
treearray.cpp:36:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 |  main(){
      |  ^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:61:9: warning: unused variable 'lca' [-Wunused-variable]
   61 |     int lca = find_lca(a[i],a[i-1]);
      |         ^~~
treearray.cpp:67:9: warning: unused variable 'lca' [-Wunused-variable]
   67 |     int lca = find_lca(a[i],a[i+1]);
      |         ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14468 KB n=5
2 Correct 10 ms 14440 KB n=100
3 Correct 9 ms 14412 KB n=100
4 Correct 10 ms 14412 KB n=100
5 Correct 10 ms 14412 KB n=100
6 Correct 10 ms 14412 KB n=100
7 Correct 11 ms 14412 KB n=100
8 Correct 10 ms 14412 KB n=100
9 Correct 10 ms 14412 KB n=100
10 Correct 10 ms 14412 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 9 ms 14412 KB n=100
13 Correct 9 ms 14428 KB n=100
14 Correct 12 ms 14412 KB n=100
15 Correct 10 ms 14412 KB n=100
16 Correct 10 ms 14412 KB n=100
17 Correct 9 ms 14412 KB n=100
18 Correct 9 ms 14412 KB n=100
19 Correct 9 ms 14396 KB n=100
20 Correct 10 ms 14412 KB n=100
21 Correct 9 ms 14412 KB n=100
22 Correct 10 ms 14412 KB n=100
23 Correct 9 ms 14412 KB n=100
24 Correct 10 ms 14412 KB n=100
25 Correct 9 ms 14412 KB n=100
26 Correct 9 ms 14412 KB n=12
27 Correct 10 ms 14412 KB n=100
28 Correct 11 ms 14540 KB n=500
29 Correct 11 ms 14540 KB n=500
30 Correct 12 ms 14540 KB n=500
31 Correct 12 ms 14532 KB n=500
32 Correct 12 ms 14560 KB n=500
33 Correct 11 ms 14600 KB n=500
34 Correct 11 ms 14540 KB n=500
35 Correct 11 ms 14540 KB n=500
36 Correct 11 ms 14512 KB n=500
37 Correct 12 ms 14560 KB n=500
38 Correct 13 ms 14536 KB n=500
39 Correct 12 ms 14540 KB n=500
40 Correct 12 ms 14544 KB n=500
41 Correct 12 ms 14540 KB n=500
42 Correct 11 ms 14540 KB n=500
43 Correct 11 ms 14540 KB n=500
44 Correct 13 ms 14524 KB n=500
45 Correct 12 ms 14540 KB n=500
46 Correct 11 ms 14540 KB n=500
47 Correct 11 ms 14540 KB n=500
48 Correct 11 ms 14540 KB n=500
49 Correct 14 ms 14540 KB n=500
50 Correct 11 ms 14540 KB n=500
51 Correct 12 ms 14556 KB n=500
52 Correct 12 ms 14540 KB n=500
53 Correct 12 ms 14540 KB n=500
54 Correct 11 ms 14540 KB n=500
55 Correct 10 ms 14424 KB n=278
56 Correct 11 ms 14540 KB n=500
57 Correct 11 ms 14576 KB n=500
58 Correct 12 ms 14540 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14468 KB n=5
2 Correct 10 ms 14440 KB n=100
3 Correct 9 ms 14412 KB n=100
4 Correct 10 ms 14412 KB n=100
5 Correct 10 ms 14412 KB n=100
6 Correct 10 ms 14412 KB n=100
7 Correct 11 ms 14412 KB n=100
8 Correct 10 ms 14412 KB n=100
9 Correct 10 ms 14412 KB n=100
10 Correct 10 ms 14412 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 9 ms 14412 KB n=100
13 Correct 9 ms 14428 KB n=100
14 Correct 12 ms 14412 KB n=100
15 Correct 10 ms 14412 KB n=100
16 Correct 10 ms 14412 KB n=100
17 Correct 9 ms 14412 KB n=100
18 Correct 9 ms 14412 KB n=100
19 Correct 9 ms 14396 KB n=100
20 Correct 10 ms 14412 KB n=100
21 Correct 9 ms 14412 KB n=100
22 Correct 10 ms 14412 KB n=100
23 Correct 9 ms 14412 KB n=100
24 Correct 10 ms 14412 KB n=100
25 Correct 9 ms 14412 KB n=100
26 Correct 9 ms 14412 KB n=12
27 Correct 10 ms 14412 KB n=100
28 Correct 11 ms 14540 KB n=500
29 Correct 11 ms 14540 KB n=500
30 Correct 12 ms 14540 KB n=500
31 Correct 12 ms 14532 KB n=500
32 Correct 12 ms 14560 KB n=500
33 Correct 11 ms 14600 KB n=500
34 Correct 11 ms 14540 KB n=500
35 Correct 11 ms 14540 KB n=500
36 Correct 11 ms 14512 KB n=500
37 Correct 12 ms 14560 KB n=500
38 Correct 13 ms 14536 KB n=500
39 Correct 12 ms 14540 KB n=500
40 Correct 12 ms 14544 KB n=500
41 Correct 12 ms 14540 KB n=500
42 Correct 11 ms 14540 KB n=500
43 Correct 11 ms 14540 KB n=500
44 Correct 13 ms 14524 KB n=500
45 Correct 12 ms 14540 KB n=500
46 Correct 11 ms 14540 KB n=500
47 Correct 11 ms 14540 KB n=500
48 Correct 11 ms 14540 KB n=500
49 Correct 14 ms 14540 KB n=500
50 Correct 11 ms 14540 KB n=500
51 Correct 12 ms 14556 KB n=500
52 Correct 12 ms 14540 KB n=500
53 Correct 12 ms 14540 KB n=500
54 Correct 11 ms 14540 KB n=500
55 Correct 10 ms 14424 KB n=278
56 Correct 11 ms 14540 KB n=500
57 Correct 11 ms 14576 KB n=500
58 Correct 12 ms 14540 KB n=500
59 Correct 17 ms 15052 KB n=2000
60 Correct 16 ms 15052 KB n=2000
61 Correct 17 ms 15052 KB n=2000
62 Correct 19 ms 15052 KB n=2000
63 Correct 17 ms 15052 KB n=2000
64 Correct 17 ms 15036 KB n=2000
65 Correct 17 ms 15052 KB n=2000
66 Correct 17 ms 15160 KB n=2000
67 Correct 18 ms 15092 KB n=2000
68 Correct 18 ms 15052 KB n=2000
69 Correct 21 ms 15040 KB n=2000
70 Correct 19 ms 15004 KB n=2000
71 Correct 17 ms 15052 KB n=2000
72 Correct 18 ms 15052 KB n=2000
73 Correct 18 ms 15000 KB n=2000
74 Correct 16 ms 15052 KB n=1844
75 Correct 17 ms 15052 KB n=2000
76 Correct 17 ms 15096 KB n=2000
77 Correct 18 ms 15052 KB n=2000
78 Correct 17 ms 14996 KB n=2000
79 Correct 17 ms 15060 KB n=2000
80 Correct 17 ms 15052 KB n=2000
81 Correct 17 ms 15052 KB n=2000
82 Correct 21 ms 15052 KB n=2000
83 Correct 17 ms 15076 KB n=2000
84 Correct 17 ms 15052 KB n=2000
85 Correct 18 ms 15052 KB n=2000
86 Correct 17 ms 15056 KB n=2000
87 Correct 16 ms 15052 KB n=2000
88 Correct 19 ms 15060 KB n=2000
89 Correct 16 ms 15180 KB n=2000
90 Correct 25 ms 15068 KB n=2000
91 Correct 19 ms 15052 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14468 KB n=5
2 Correct 10 ms 14440 KB n=100
3 Correct 9 ms 14412 KB n=100
4 Correct 10 ms 14412 KB n=100
5 Correct 10 ms 14412 KB n=100
6 Correct 10 ms 14412 KB n=100
7 Correct 11 ms 14412 KB n=100
8 Correct 10 ms 14412 KB n=100
9 Correct 10 ms 14412 KB n=100
10 Correct 10 ms 14412 KB n=100
11 Correct 9 ms 14412 KB n=100
12 Correct 9 ms 14412 KB n=100
13 Correct 9 ms 14428 KB n=100
14 Correct 12 ms 14412 KB n=100
15 Correct 10 ms 14412 KB n=100
16 Correct 10 ms 14412 KB n=100
17 Correct 9 ms 14412 KB n=100
18 Correct 9 ms 14412 KB n=100
19 Correct 9 ms 14396 KB n=100
20 Correct 10 ms 14412 KB n=100
21 Correct 9 ms 14412 KB n=100
22 Correct 10 ms 14412 KB n=100
23 Correct 9 ms 14412 KB n=100
24 Correct 10 ms 14412 KB n=100
25 Correct 9 ms 14412 KB n=100
26 Correct 9 ms 14412 KB n=12
27 Correct 10 ms 14412 KB n=100
28 Correct 11 ms 14540 KB n=500
29 Correct 11 ms 14540 KB n=500
30 Correct 12 ms 14540 KB n=500
31 Correct 12 ms 14532 KB n=500
32 Correct 12 ms 14560 KB n=500
33 Correct 11 ms 14600 KB n=500
34 Correct 11 ms 14540 KB n=500
35 Correct 11 ms 14540 KB n=500
36 Correct 11 ms 14512 KB n=500
37 Correct 12 ms 14560 KB n=500
38 Correct 13 ms 14536 KB n=500
39 Correct 12 ms 14540 KB n=500
40 Correct 12 ms 14544 KB n=500
41 Correct 12 ms 14540 KB n=500
42 Correct 11 ms 14540 KB n=500
43 Correct 11 ms 14540 KB n=500
44 Correct 13 ms 14524 KB n=500
45 Correct 12 ms 14540 KB n=500
46 Correct 11 ms 14540 KB n=500
47 Correct 11 ms 14540 KB n=500
48 Correct 11 ms 14540 KB n=500
49 Correct 14 ms 14540 KB n=500
50 Correct 11 ms 14540 KB n=500
51 Correct 12 ms 14556 KB n=500
52 Correct 12 ms 14540 KB n=500
53 Correct 12 ms 14540 KB n=500
54 Correct 11 ms 14540 KB n=500
55 Correct 10 ms 14424 KB n=278
56 Correct 11 ms 14540 KB n=500
57 Correct 11 ms 14576 KB n=500
58 Correct 12 ms 14540 KB n=500
59 Correct 17 ms 15052 KB n=2000
60 Correct 16 ms 15052 KB n=2000
61 Correct 17 ms 15052 KB n=2000
62 Correct 19 ms 15052 KB n=2000
63 Correct 17 ms 15052 KB n=2000
64 Correct 17 ms 15036 KB n=2000
65 Correct 17 ms 15052 KB n=2000
66 Correct 17 ms 15160 KB n=2000
67 Correct 18 ms 15092 KB n=2000
68 Correct 18 ms 15052 KB n=2000
69 Correct 21 ms 15040 KB n=2000
70 Correct 19 ms 15004 KB n=2000
71 Correct 17 ms 15052 KB n=2000
72 Correct 18 ms 15052 KB n=2000
73 Correct 18 ms 15000 KB n=2000
74 Correct 16 ms 15052 KB n=1844
75 Correct 17 ms 15052 KB n=2000
76 Correct 17 ms 15096 KB n=2000
77 Correct 18 ms 15052 KB n=2000
78 Correct 17 ms 14996 KB n=2000
79 Correct 17 ms 15060 KB n=2000
80 Correct 17 ms 15052 KB n=2000
81 Correct 17 ms 15052 KB n=2000
82 Correct 21 ms 15052 KB n=2000
83 Correct 17 ms 15076 KB n=2000
84 Correct 17 ms 15052 KB n=2000
85 Correct 18 ms 15052 KB n=2000
86 Correct 17 ms 15056 KB n=2000
87 Correct 16 ms 15052 KB n=2000
88 Correct 19 ms 15060 KB n=2000
89 Correct 16 ms 15180 KB n=2000
90 Correct 25 ms 15068 KB n=2000
91 Correct 19 ms 15052 KB n=2000
92 Correct 1533 ms 84452 KB n=200000
93 Correct 1716 ms 91620 KB n=200000
94 Correct 1293 ms 98912 KB n=200000
95 Correct 1459 ms 90672 KB n=200000
96 Correct 1544 ms 90720 KB n=200000
97 Correct 1814 ms 94972 KB n=200000
98 Correct 1490 ms 90748 KB n=200000
99 Correct 1901 ms 91084 KB n=200000
100 Correct 1522 ms 90904 KB n=200000
101 Correct 1235 ms 99596 KB n=200000
102 Correct 1184 ms 92212 KB n=200000
103 Correct 1197 ms 92144 KB n=200000
104 Correct 1250 ms 92148 KB n=200000
105 Correct 1232 ms 92748 KB n=200000
106 Correct 1352 ms 92556 KB n=200000
107 Correct 1314 ms 92664 KB n=200000
108 Correct 1594 ms 91160 KB n=200000
109 Correct 1551 ms 91044 KB n=200000
110 Correct 1741 ms 91084 KB n=200000
111 Correct 1489 ms 90268 KB n=200000
112 Correct 1358 ms 98900 KB n=200000
113 Correct 1791 ms 95012 KB n=200000
114 Correct 1507 ms 90312 KB n=200000
115 Correct 2016 ms 93116 KB n=200000
116 Correct 1510 ms 90928 KB n=200000
117 Correct 1217 ms 99148 KB n=200000
118 Correct 1910 ms 93836 KB n=200000
119 Correct 1493 ms 90876 KB n=200000
120 Correct 1182 ms 98544 KB n=200000
121 Correct 1108 ms 98628 KB n=200000
122 Correct 1063 ms 98856 KB n=200000
123 Correct 1281 ms 92456 KB n=200000
124 Correct 353 ms 34756 KB n=25264