oj.uz

Submission #502047

# Submission time Handle Problem Language Result Execution time Memory
502047 2022-01-05T07:08:41 Z ismoilov Birthday gift (IZhO18_treearray) C++14
100 / 100
 1087 ms 87096 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
const int maxx = 2e5+5;
vector <int> g[maxx];
int a[maxx], d[maxx], lc[maxx][20];
set <int> A[maxx], B[maxx];
int n, m, q;

void dfs(int v, int p = 0){
	lc[v][0] = p;
	fpp(i,1,18)
		lc[v][i] = lc[lc[v][i-1]][i-1];
	for(auto it : g[v]){
		if(it != p){
			d[it] = d[v]+1;
			dfs(it, v);
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v])
		swap(u, v);
	int k = d[u] - d[v];
	fmm(i,18,0){
		if(k>>i & 1)
			u = lc[u][i];
	}
	if(u == v)
		return u;
	fmm(i,18,0){
		if(lc[u][i] != lc[v][i])
			u = lc[u][i], v = lc[v][i];
	}
	return lc[u][0];
}

void upd(int id, int v){
	if(id > 1){
		int y = lca(a[id], a[id-1]);
		A[y].erase(id-1);
		A[lca(v, a[id-1])].insert(id-1);
	}
	if(id < m){
		int y = lca(a[id], a[id+1]);
		A[y].erase(id);
		A[lca(v, a[id+1])].insert(id);
	}
	B[a[id]].erase(id);
	B[v].insert(id);
	a[id] = v;
}

void get(int l, int r, int v){
	auto it = B[v].lower_bound(l);
	if(it != B[v].end() && *it <= r){
		cout << *it << " " << *it << "\n";
		return;
	}
	it = A[v].lower_bound(l);
	if(it != A[v].end() && *it+1 <= r){
		cout << *it << " " << *it+1 << "\n";
		return;
	}
	cout << "-1 -1\n";
}

void S()
{
//	int n, m, q;
	cin >> n >> m >> q;
	fp(i,1,n){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1);
	fpp(i,1,m)
		cin >> a[i];
	fpp(i,1,m){
		int x = lca(a[i], a[i+1]);
	//	cout << i << " " << x << "\n";
		if(i < m)
			A[x].insert(i);
		B[a[i]].insert(i);
	}
/*	fpp(i,1,n){
		cout << i << " ";
		for(auto it : A[i])
			cout << it << " ";
		cout << "\n";
	}*/
	while(q --){
		int t;
		cin >> t;
		if(t == 1){
			int id, v;
			cin >> id >> v;
			upd(id, v);
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			get(l, r, v);
		}
	}
}
int main()
{
	IOS;
	S();
}

Compilation message

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:18:2: note: in expansion of macro 'fpp'
   18 |  fpp(i,1,18)
      |  ^~~
treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
      |                            ^
treearray.cpp:32:2: note: in expansion of macro 'fmm'
   32 |  fmm(i,18,0){
      |  ^~~
treearray.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
      |                            ^
treearray.cpp:38:2: note: in expansion of macro 'fmm'
   38 |  fmm(i,18,0){
      |  ^~~
treearray.cpp: In function 'void S()':
treearray.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
treearray.cpp:79:2: note: in expansion of macro 'fp'
   79 |  fp(i,1,n){
      |  ^~
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:86:2: note: in expansion of macro 'fpp'
   86 |  fpp(i,1,m)
      |  ^~~
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:88:2: note: in expansion of macro 'fpp'
   88 |  fpp(i,1,m){
      |  ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23800 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 15 ms 23804 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 13 ms 23756 KB n=100
7 Correct 13 ms 23808 KB n=100
8 Correct 12 ms 23796 KB n=100
9 Correct 15 ms 23800 KB n=100
10 Correct 11 ms 23756 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 11 ms 23804 KB n=100
13 Correct 11 ms 23800 KB n=100
14 Correct 12 ms 23796 KB n=100
15 Correct 12 ms 23808 KB n=100
16 Correct 13 ms 23728 KB n=100
17 Correct 13 ms 23812 KB n=100
18 Correct 12 ms 23748 KB n=100
19 Correct 13 ms 23788 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 11 ms 23820 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23800 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23784 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 13 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23800 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 15 ms 23804 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 13 ms 23756 KB n=100
7 Correct 13 ms 23808 KB n=100
8 Correct 12 ms 23796 KB n=100
9 Correct 15 ms 23800 KB n=100
10 Correct 11 ms 23756 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 11 ms 23804 KB n=100
13 Correct 11 ms 23800 KB n=100
14 Correct 12 ms 23796 KB n=100
15 Correct 12 ms 23808 KB n=100
16 Correct 13 ms 23728 KB n=100
17 Correct 13 ms 23812 KB n=100
18 Correct 12 ms 23748 KB n=100
19 Correct 13 ms 23788 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 11 ms 23820 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23800 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23784 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 12 ms 23944 KB n=500
30 Correct 13 ms 23808 KB n=500
31 Correct 12 ms 23876 KB n=500
32 Correct 13 ms 23880 KB n=500
33 Correct 13 ms 23932 KB n=500
34 Correct 12 ms 23808 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23808 KB n=500
37 Correct 14 ms 23804 KB n=500
38 Correct 13 ms 23876 KB n=500
39 Correct 12 ms 23896 KB n=500
40 Correct 12 ms 23940 KB n=500
41 Correct 12 ms 23840 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 15 ms 23804 KB n=500
44 Correct 13 ms 23928 KB n=500
45 Correct 13 ms 23884 KB n=500
46 Correct 12 ms 23944 KB n=500
47 Correct 13 ms 23956 KB n=500
48 Correct 13 ms 23808 KB n=500
49 Correct 13 ms 23884 KB n=500
50 Correct 15 ms 23820 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 15 ms 24004 KB n=500
53 Correct 14 ms 23876 KB n=500
54 Correct 13 ms 23936 KB n=500
55 Correct 13 ms 23848 KB n=278
56 Correct 13 ms 23884 KB n=500
57 Correct 13 ms 23944 KB n=500
58 Correct 13 ms 23812 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23800 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 15 ms 23804 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 13 ms 23756 KB n=100
7 Correct 13 ms 23808 KB n=100
8 Correct 12 ms 23796 KB n=100
9 Correct 15 ms 23800 KB n=100
10 Correct 11 ms 23756 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 11 ms 23804 KB n=100
13 Correct 11 ms 23800 KB n=100
14 Correct 12 ms 23796 KB n=100
15 Correct 12 ms 23808 KB n=100
16 Correct 13 ms 23728 KB n=100
17 Correct 13 ms 23812 KB n=100
18 Correct 12 ms 23748 KB n=100
19 Correct 13 ms 23788 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 11 ms 23820 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23800 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23784 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 12 ms 23944 KB n=500
30 Correct 13 ms 23808 KB n=500
31 Correct 12 ms 23876 KB n=500
32 Correct 13 ms 23880 KB n=500
33 Correct 13 ms 23932 KB n=500
34 Correct 12 ms 23808 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23808 KB n=500
37 Correct 14 ms 23804 KB n=500
38 Correct 13 ms 23876 KB n=500
39 Correct 12 ms 23896 KB n=500
40 Correct 12 ms 23940 KB n=500
41 Correct 12 ms 23840 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 15 ms 23804 KB n=500
44 Correct 13 ms 23928 KB n=500
45 Correct 13 ms 23884 KB n=500
46 Correct 12 ms 23944 KB n=500
47 Correct 13 ms 23956 KB n=500
48 Correct 13 ms 23808 KB n=500
49 Correct 13 ms 23884 KB n=500
50 Correct 15 ms 23820 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 15 ms 24004 KB n=500
53 Correct 14 ms 23876 KB n=500
54 Correct 13 ms 23936 KB n=500
55 Correct 13 ms 23848 KB n=278
56 Correct 13 ms 23884 KB n=500
57 Correct 13 ms 23944 KB n=500
58 Correct 13 ms 23812 KB n=500
59 Correct 15 ms 24264 KB n=2000
60 Correct 19 ms 24388 KB n=2000
61 Correct 17 ms 24268 KB n=2000
62 Correct 16 ms 24324 KB n=2000
63 Correct 15 ms 24268 KB n=2000
64 Correct 16 ms 24276 KB n=2000
65 Correct 15 ms 24264 KB n=2000
66 Correct 16 ms 24396 KB n=2000
67 Correct 16 ms 24268 KB n=2000
68 Correct 15 ms 24316 KB n=2000
69 Correct 14 ms 24260 KB n=2000
70 Correct 14 ms 24276 KB n=2000
71 Correct 19 ms 24260 KB n=2000
72 Correct 17 ms 24184 KB n=2000
73 Correct 15 ms 24276 KB n=2000
74 Correct 14 ms 24200 KB n=1844
75 Correct 14 ms 24264 KB n=2000
76 Correct 15 ms 24196 KB n=2000
77 Correct 15 ms 24260 KB n=2000
78 Correct 16 ms 24260 KB n=2000
79 Correct 16 ms 24268 KB n=2000
80 Correct 19 ms 24268 KB n=2000
81 Correct 15 ms 24292 KB n=2000
82 Correct 15 ms 24196 KB n=2000
83 Correct 14 ms 24260 KB n=2000
84 Correct 15 ms 24264 KB n=2000
85 Correct 20 ms 24268 KB n=2000
86 Correct 19 ms 24312 KB n=2000
87 Correct 15 ms 24260 KB n=2000
88 Correct 15 ms 24400 KB n=2000
89 Correct 17 ms 24396 KB n=2000
90 Correct 17 ms 24388 KB n=2000
91 Correct 17 ms 24296 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23800 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 15 ms 23804 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 13 ms 23756 KB n=100
7 Correct 13 ms 23808 KB n=100
8 Correct 12 ms 23796 KB n=100
9 Correct 15 ms 23800 KB n=100
10 Correct 11 ms 23756 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 11 ms 23804 KB n=100
13 Correct 11 ms 23800 KB n=100
14 Correct 12 ms 23796 KB n=100
15 Correct 12 ms 23808 KB n=100
16 Correct 13 ms 23728 KB n=100
17 Correct 13 ms 23812 KB n=100
18 Correct 12 ms 23748 KB n=100
19 Correct 13 ms 23788 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 11 ms 23820 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23800 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23784 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 12 ms 23944 KB n=500
30 Correct 13 ms 23808 KB n=500
31 Correct 12 ms 23876 KB n=500
32 Correct 13 ms 23880 KB n=500
33 Correct 13 ms 23932 KB n=500
34 Correct 12 ms 23808 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23808 KB n=500
37 Correct 14 ms 23804 KB n=500
38 Correct 13 ms 23876 KB n=500
39 Correct 12 ms 23896 KB n=500
40 Correct 12 ms 23940 KB n=500
41 Correct 12 ms 23840 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 15 ms 23804 KB n=500
44 Correct 13 ms 23928 KB n=500
45 Correct 13 ms 23884 KB n=500
46 Correct 12 ms 23944 KB n=500
47 Correct 13 ms 23956 KB n=500
48 Correct 13 ms 23808 KB n=500
49 Correct 13 ms 23884 KB n=500
50 Correct 15 ms 23820 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 15 ms 24004 KB n=500
53 Correct 14 ms 23876 KB n=500
54 Correct 13 ms 23936 KB n=500
55 Correct 13 ms 23848 KB n=278
56 Correct 13 ms 23884 KB n=500
57 Correct 13 ms 23944 KB n=500
58 Correct 13 ms 23812 KB n=500
59 Correct 15 ms 24264 KB n=2000
60 Correct 19 ms 24388 KB n=2000
61 Correct 17 ms 24268 KB n=2000
62 Correct 16 ms 24324 KB n=2000
63 Correct 15 ms 24268 KB n=2000
64 Correct 16 ms 24276 KB n=2000
65 Correct 15 ms 24264 KB n=2000
66 Correct 16 ms 24396 KB n=2000
67 Correct 16 ms 24268 KB n=2000
68 Correct 15 ms 24316 KB n=2000
69 Correct 14 ms 24260 KB n=2000
70 Correct 14 ms 24276 KB n=2000
71 Correct 19 ms 24260 KB n=2000
72 Correct 17 ms 24184 KB n=2000
73 Correct 15 ms 24276 KB n=2000
74 Correct 14 ms 24200 KB n=1844
75 Correct 14 ms 24264 KB n=2000
76 Correct 15 ms 24196 KB n=2000
77 Correct 15 ms 24260 KB n=2000
78 Correct 16 ms 24260 KB n=2000
79 Correct 16 ms 24268 KB n=2000
80 Correct 19 ms 24268 KB n=2000
81 Correct 15 ms 24292 KB n=2000
82 Correct 15 ms 24196 KB n=2000
83 Correct 14 ms 24260 KB n=2000
84 Correct 15 ms 24264 KB n=2000
85 Correct 20 ms 24268 KB n=2000
86 Correct 19 ms 24312 KB n=2000
87 Correct 15 ms 24260 KB n=2000
88 Correct 15 ms 24400 KB n=2000
89 Correct 17 ms 24396 KB n=2000
90 Correct 17 ms 24388 KB n=2000
91 Correct 17 ms 24296 KB n=2000
92 Correct 727 ms 74468 KB n=200000
93 Correct 998 ms 80972 KB n=200000
94 Correct 979 ms 85424 KB n=200000
95 Correct 670 ms 74296 KB n=200000
96 Correct 638 ms 74348 KB n=200000
97 Correct 949 ms 79788 KB n=200000
98 Correct 710 ms 74400 KB n=200000
99 Correct 901 ms 74568 KB n=200000
100 Correct 674 ms 74428 KB n=200000
101 Correct 903 ms 87096 KB n=200000
102 Correct 424 ms 75460 KB n=200000
103 Correct 418 ms 75628 KB n=200000
104 Correct 436 ms 75472 KB n=200000
105 Correct 414 ms 75940 KB n=200000
106 Correct 435 ms 75940 KB n=200000
107 Correct 403 ms 75972 KB n=200000
108 Correct 765 ms 74400 KB n=200000
109 Correct 765 ms 74540 KB n=200000
110 Correct 746 ms 74352 KB n=200000
111 Correct 660 ms 73784 KB n=200000
112 Correct 887 ms 85688 KB n=200000
113 Correct 978 ms 79564 KB n=200000
114 Correct 714 ms 73812 KB n=200000
115 Correct 1087 ms 76844 KB n=200000
116 Correct 721 ms 74496 KB n=200000
117 Correct 933 ms 86248 KB n=200000
118 Correct 970 ms 78216 KB n=200000
119 Correct 679 ms 74516 KB n=200000
120 Correct 935 ms 86244 KB n=200000
121 Correct 886 ms 86140 KB n=200000
122 Correct 884 ms 86424 KB n=200000
123 Correct 430 ms 75720 KB n=200000
124 Correct 226 ms 39024 KB n=25264