oj.uz

Submission #672233

# Submission time Handle Problem Language Result Execution time Memory
672233 2022-12-15T06:40:29 Z Baytoro Birthday gift (IZhO18_treearray) C++17
100 / 100
 1323 ms 97496 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e18,mod=1e9+7;
int n,m,q;
int p[200005][21],depth[200005];
vector<int> g[200005];
void dfs(int x, int par){
	p[x][0]=par;
	depth[x]=depth[par]+1;
	for(auto it: g[x]){
		if(it==par) continue;
		dfs(it,x);
	}
}
int lca(int a, int b){
	if(depth[a]<depth[b]) swap(a,b);
	int k=depth[a]-depth[b];
	for(int i=20;i>=0;i--){
		if(k&(1<<i))
			a=p[a][i];
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--){
		if(p[a][i]!=p[b][i]){
			a=p[a][i];
			b=p[b][i];
		}
	}
	return p[a][0];
}
int ar[200005];
set<int> a[200005],b[200005];
void solve(){
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1,1);
	for(int l=1;l<21;l++){
		for(int i=1;i<=n;i++){
			p[i][l]=p[p[i][l-1]][l-1];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>ar[i];
		a[ar[i]].insert(i);
		if(i>1)
			b[lca(ar[i],ar[i-1])].insert(i-1);
	}
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			int p,v;cin>>p>>v;
			a[ar[p]].erase(p);
			a[v].insert(p);
			if(p>1){
				b[lca(ar[p],ar[p-1])].erase(p-1);
				b[lca(v,ar[p-1])].insert(p-1);
			}
			if(p<m){
				b[lca(ar[p],ar[p+1])].erase(p);
				b[lca(v,ar[p+1])].insert(p);
			}
			ar[p]=v;
		}
		else{
			int l,r,v;
			cin>>l>>r>>v;
			auto it = a[v].lower_bound(l);
			if(it!=a[v].end() && *it<=r){
				cout<<*it<<' '<<*it<<endl;
			}
			else{
				it=b[v].lower_bound(l);
				if(it!=b[v].end() && *it<r){
					cout<<*it<<' '<<*it+1<<endl;
				}
				else{
					cout<<"-1 -1\n";
				}
			}
		}
	}
}
main(){
	ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

treearray.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main(){
      | ^~~~
treearray.cpp: In function 'void fopn(std::string)':
treearray.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23764 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 12 ms 23856 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 13 ms 23824 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 12 ms 23828 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 12 ms 23820 KB n=100
21 Correct 12 ms 23816 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23820 KB n=100
24 Correct 13 ms 23860 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 12 ms 23764 KB n=100
28 Correct 13 ms 23960 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23892 KB n=500
32 Correct 13 ms 24156 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 13 ms 23960 KB n=500
36 Correct 12 ms 23892 KB n=500
37 Correct 12 ms 23960 KB n=500
38 Correct 13 ms 23956 KB n=500
39 Correct 13 ms 23892 KB n=500
40 Correct 13 ms 23964 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23952 KB n=500
45 Correct 13 ms 23956 KB n=500
46 Correct 13 ms 23892 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23968 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 13 ms 23892 KB n=500
52 Correct 12 ms 23960 KB n=500
53 Correct 13 ms 23928 KB n=500
54 Correct 13 ms 23912 KB n=500
55 Correct 12 ms 23892 KB n=278
56 Correct 12 ms 23952 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 12 ms 23952 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23764 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 12 ms 23856 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 13 ms 23824 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 12 ms 23828 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 12 ms 23820 KB n=100
21 Correct 12 ms 23816 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23820 KB n=100
24 Correct 13 ms 23860 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 12 ms 23764 KB n=100
28 Correct 13 ms 23960 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23892 KB n=500
32 Correct 13 ms 24156 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 13 ms 23960 KB n=500
36 Correct 12 ms 23892 KB n=500
37 Correct 12 ms 23960 KB n=500
38 Correct 13 ms 23956 KB n=500
39 Correct 13 ms 23892 KB n=500
40 Correct 13 ms 23964 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23952 KB n=500
45 Correct 13 ms 23956 KB n=500
46 Correct 13 ms 23892 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23968 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 13 ms 23892 KB n=500
52 Correct 12 ms 23960 KB n=500
53 Correct 13 ms 23928 KB n=500
54 Correct 13 ms 23912 KB n=500
55 Correct 12 ms 23892 KB n=278
56 Correct 12 ms 23952 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 12 ms 23952 KB n=500
59 Correct 15 ms 24452 KB n=2000
60 Correct 16 ms 24468 KB n=2000
61 Correct 17 ms 24532 KB n=2000
62 Correct 16 ms 24472 KB n=2000
63 Correct 16 ms 24404 KB n=2000
64 Correct 15 ms 24424 KB n=2000
65 Correct 16 ms 24472 KB n=2000
66 Correct 15 ms 24552 KB n=2000
67 Correct 15 ms 24472 KB n=2000
68 Correct 15 ms 24556 KB n=2000
69 Correct 15 ms 24404 KB n=2000
70 Correct 15 ms 24480 KB n=2000
71 Correct 15 ms 24424 KB n=2000
72 Correct 14 ms 24404 KB n=2000
73 Correct 14 ms 24472 KB n=2000
74 Correct 15 ms 24404 KB n=1844
75 Correct 14 ms 24432 KB n=2000
76 Correct 15 ms 24472 KB n=2000
77 Correct 15 ms 24404 KB n=2000
78 Correct 16 ms 24404 KB n=2000
79 Correct 15 ms 24404 KB n=2000
80 Correct 15 ms 24472 KB n=2000
81 Correct 16 ms 24532 KB n=2000
82 Correct 15 ms 24404 KB n=2000
83 Correct 15 ms 24524 KB n=2000
84 Correct 16 ms 24404 KB n=2000
85 Correct 16 ms 24452 KB n=2000
86 Correct 16 ms 24532 KB n=2000
87 Correct 16 ms 24416 KB n=2000
88 Correct 14 ms 24532 KB n=2000
89 Correct 15 ms 24584 KB n=2000
90 Correct 15 ms 24468 KB n=2000
91 Correct 14 ms 24472 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23764 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 12 ms 23856 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 13 ms 23824 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 12 ms 23828 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 12 ms 23820 KB n=100
21 Correct 12 ms 23816 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23820 KB n=100
24 Correct 13 ms 23860 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 12 ms 23764 KB n=100
28 Correct 13 ms 23960 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23892 KB n=500
32 Correct 13 ms 24156 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 13 ms 23960 KB n=500
36 Correct 12 ms 23892 KB n=500
37 Correct 12 ms 23960 KB n=500
38 Correct 13 ms 23956 KB n=500
39 Correct 13 ms 23892 KB n=500
40 Correct 13 ms 23964 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23952 KB n=500
45 Correct 13 ms 23956 KB n=500
46 Correct 13 ms 23892 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23968 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 13 ms 23892 KB n=500
52 Correct 12 ms 23960 KB n=500
53 Correct 13 ms 23928 KB n=500
54 Correct 13 ms 23912 KB n=500
55 Correct 12 ms 23892 KB n=278
56 Correct 12 ms 23952 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 12 ms 23952 KB n=500
59 Correct 15 ms 24452 KB n=2000
60 Correct 16 ms 24468 KB n=2000
61 Correct 17 ms 24532 KB n=2000
62 Correct 16 ms 24472 KB n=2000
63 Correct 16 ms 24404 KB n=2000
64 Correct 15 ms 24424 KB n=2000
65 Correct 16 ms 24472 KB n=2000
66 Correct 15 ms 24552 KB n=2000
67 Correct 15 ms 24472 KB n=2000
68 Correct 15 ms 24556 KB n=2000
69 Correct 15 ms 24404 KB n=2000
70 Correct 15 ms 24480 KB n=2000
71 Correct 15 ms 24424 KB n=2000
72 Correct 14 ms 24404 KB n=2000
73 Correct 14 ms 24472 KB n=2000
74 Correct 15 ms 24404 KB n=1844
75 Correct 14 ms 24432 KB n=2000
76 Correct 15 ms 24472 KB n=2000
77 Correct 15 ms 24404 KB n=2000
78 Correct 16 ms 24404 KB n=2000
79 Correct 15 ms 24404 KB n=2000
80 Correct 15 ms 24472 KB n=2000
81 Correct 16 ms 24532 KB n=2000
82 Correct 15 ms 24404 KB n=2000
83 Correct 15 ms 24524 KB n=2000
84 Correct 16 ms 24404 KB n=2000
85 Correct 16 ms 24452 KB n=2000
86 Correct 16 ms 24532 KB n=2000
87 Correct 16 ms 24416 KB n=2000
88 Correct 14 ms 24532 KB n=2000
89 Correct 15 ms 24584 KB n=2000
90 Correct 15 ms 24468 KB n=2000
91 Correct 14 ms 24472 KB n=2000
92 Correct 720 ms 89812 KB n=200000
93 Correct 1095 ms 93608 KB n=200000
94 Correct 1043 ms 96368 KB n=200000
95 Correct 713 ms 89588 KB n=200000
96 Correct 691 ms 89564 KB n=200000
97 Correct 1119 ms 92868 KB n=200000
98 Correct 736 ms 89716 KB n=200000
99 Correct 898 ms 89384 KB n=200000
100 Correct 703 ms 89796 KB n=200000
101 Correct 1031 ms 97432 KB n=200000
102 Correct 471 ms 90756 KB n=200000
103 Correct 466 ms 90740 KB n=200000
104 Correct 459 ms 90744 KB n=200000
105 Correct 454 ms 90504 KB n=200000
106 Correct 452 ms 90596 KB n=200000
107 Correct 455 ms 90672 KB n=200000
108 Correct 849 ms 89632 KB n=200000
109 Correct 854 ms 89404 KB n=200000
110 Correct 857 ms 89480 KB n=200000
111 Correct 732 ms 89432 KB n=200000
112 Correct 1049 ms 96696 KB n=200000
113 Correct 1104 ms 92676 KB n=200000
114 Correct 746 ms 89560 KB n=200000
115 Correct 1323 ms 90848 KB n=200000
116 Correct 821 ms 89340 KB n=200000
117 Correct 1006 ms 96788 KB n=200000
118 Correct 1123 ms 91596 KB n=200000
119 Correct 665 ms 89380 KB n=200000
120 Correct 1006 ms 97012 KB n=200000
121 Correct 985 ms 96904 KB n=200000
122 Correct 1002 ms 97496 KB n=200000
123 Correct 451 ms 90444 KB n=200000
124 Correct 258 ms 41288 KB n=25264