oj.uz

Submission #385600

# Submission time Handle Problem Language Result Execution time Memory
385600 2021-04-04T15:51:37 Z patrikpavic2 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1253 ms 78188 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;
const int LOG = 18;

int par[N][LOG], n, m, q;
int A[N], B[N], dep[N];
set < int > gdje[N], sam[N];
vector < int > v[N];

void precompute(){
	for(int j = 1;j < LOG;j++)
		for(int i = 1;i <= n;i++)
			par[i][j] = par[par[i][j - 1]][j - 1];
}

void dfs(int x, int lst){
	par[x][0] = lst;
	dep[x] = dep[lst] + 1;
	for(int y : v[x])
		if(y != lst) 
			dfs(y, x);
}

int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = LOG - 1;i >= 0;i--)
		if(dep[x] - (1 << i) >= dep[y])
			x = par[x][i];
	if(x == y) return x;
	for(int i = LOG - 1;i >= 0;i--)
		if(par[x][i] != par[y][i])
			x = par[x][i],
			y = par[y][i];
	return par[x][0];
}

void update(int i){
	if(i < 1 || i >= m) return;
	if(B[i]) gdje[B[i]].erase(i);
	B[i] = lca(A[i], A[i + 1]);
	gdje[B[i]].insert(i);
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	dfs(1, 1); precompute();
	for(int i = 1;i <= m;i++){
		scanf("%d", A + i);
		sam[A[i]].insert(i);
	}
	for(int i = 1;i < m;i++) 
		update(i);
	for(int i = 0;i < q;i++){
		int ty; scanf("%d", &ty);
		if(ty == 1){
			int x, pos; scanf("%d%d", &pos, &x);
			sam[A[pos]].erase(pos);
			A[pos] = x; update(pos); update(pos - 1);
			sam[A[pos]].insert(pos);
		}
		else{
			int l, r, x; scanf("%d%d%d", &l, &r, &x);
			if(sam[x].lower_bound(l) != sam[x].end() && *sam[x].lower_bound(l) <= r){
				int tmp = *sam[x].lower_bound(l);
				printf("%d %d\n", tmp, tmp);
			}
			else if(gdje[x].lower_bound(l) != gdje[x].end() && *gdje[x].lower_bound(l) < r){
				int tmp = *gdje[x].lower_bound(l);
				printf("%d %d\n", tmp, tmp + 1);
			}
			else{
				printf("-1 -1\n");
			}
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:66:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
treearray.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |    int x, pos; scanf("%d%d", &pos, &x);
      |                ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:74:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |    int l, r, x; scanf("%d%d%d", &l, &r, &x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB n=5
2 Correct 18 ms 23916 KB n=100
3 Correct 19 ms 23916 KB n=100
4 Correct 19 ms 23916 KB n=100
5 Correct 18 ms 23916 KB n=100
6 Correct 17 ms 23856 KB n=100
7 Correct 16 ms 23916 KB n=100
8 Correct 18 ms 23916 KB n=100
9 Correct 15 ms 23916 KB n=100
10 Correct 17 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 18 ms 23916 KB n=100
15 Correct 18 ms 23916 KB n=100
16 Correct 16 ms 23916 KB n=100
17 Correct 18 ms 23916 KB n=100
18 Correct 15 ms 23916 KB n=100
19 Correct 16 ms 23972 KB n=100
20 Correct 20 ms 23900 KB n=100
21 Correct 16 ms 23916 KB n=100
22 Correct 16 ms 23916 KB n=100
23 Correct 16 ms 23916 KB n=100
24 Correct 18 ms 23912 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 16 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 24044 KB n=500
29 Correct 17 ms 24044 KB n=500
30 Correct 17 ms 24044 KB n=500
31 Correct 18 ms 24044 KB n=500
32 Correct 19 ms 24044 KB n=500
33 Correct 18 ms 24044 KB n=500
34 Correct 17 ms 24044 KB n=500
35 Correct 16 ms 24044 KB n=500
36 Correct 16 ms 24044 KB n=500
37 Correct 17 ms 24044 KB n=500
38 Correct 17 ms 24044 KB n=500
39 Correct 17 ms 24044 KB n=500
40 Correct 18 ms 24044 KB n=500
41 Correct 16 ms 24044 KB n=500
42 Correct 17 ms 24044 KB n=500
43 Correct 17 ms 24044 KB n=500
44 Correct 17 ms 24044 KB n=500
45 Correct 16 ms 24044 KB n=500
46 Correct 16 ms 24044 KB n=500
47 Correct 17 ms 24044 KB n=500
48 Correct 17 ms 24044 KB n=500
49 Correct 17 ms 24044 KB n=500
50 Correct 19 ms 24044 KB n=500
51 Correct 16 ms 24044 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 16 ms 24044 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 18 ms 23916 KB n=278
56 Correct 16 ms 24044 KB n=500
57 Correct 17 ms 24172 KB n=500
58 Correct 17 ms 24044 KB n=500
59 Correct 20 ms 24300 KB n=2000
60 Correct 20 ms 24428 KB n=2000
61 Correct 20 ms 24428 KB n=2000
62 Correct 22 ms 24428 KB n=2000
63 Correct 20 ms 24300 KB n=2000
64 Correct 19 ms 24428 KB n=2000
65 Correct 20 ms 24300 KB n=2000
66 Correct 20 ms 24428 KB n=2000
67 Correct 20 ms 24300 KB n=2000
68 Correct 19 ms 24428 KB n=2000
69 Correct 19 ms 24300 KB n=2000
70 Correct 21 ms 24300 KB n=2000
71 Correct 19 ms 24300 KB n=2000
72 Correct 19 ms 24300 KB n=2000
73 Correct 21 ms 24300 KB n=2000
74 Correct 19 ms 24300 KB n=1844
75 Correct 21 ms 24300 KB n=2000
76 Correct 21 ms 24300 KB n=2000
77 Correct 24 ms 24300 KB n=2000
78 Correct 20 ms 24300 KB n=2000
79 Correct 21 ms 24428 KB n=2000
80 Correct 19 ms 24428 KB n=2000
81 Correct 21 ms 24452 KB n=2000
82 Correct 20 ms 24300 KB n=2000
83 Correct 20 ms 24428 KB n=2000
84 Correct 20 ms 24300 KB n=2000
85 Correct 20 ms 24428 KB n=2000
86 Correct 19 ms 24428 KB n=2000
87 Correct 23 ms 24300 KB n=2000
88 Correct 20 ms 24428 KB n=2000
89 Correct 24 ms 24428 KB n=2000
90 Correct 19 ms 24428 KB n=2000
91 Correct 18 ms 24300 KB n=2000
92 Correct 815 ms 69392 KB n=200000
93 Correct 1058 ms 72944 KB n=200000
94 Correct 1012 ms 76396 KB n=200000
95 Correct 812 ms 69040 KB n=200000
96 Correct 832 ms 69232 KB n=200000
97 Correct 1158 ms 72148 KB n=200000
98 Correct 809 ms 69088 KB n=200000
99 Correct 937 ms 68608 KB n=200000
100 Correct 796 ms 69220 KB n=200000
101 Correct 1045 ms 77548 KB n=200000
102 Correct 537 ms 69996 KB n=200000
103 Correct 561 ms 70252 KB n=200000
104 Correct 556 ms 70380 KB n=200000
105 Correct 560 ms 70140 KB n=200000
106 Correct 588 ms 69996 KB n=200000
107 Correct 732 ms 70124 KB n=200000
108 Correct 970 ms 69084 KB n=200000
109 Correct 1089 ms 68960 KB n=200000
110 Correct 1014 ms 68972 KB n=200000
111 Correct 913 ms 69216 KB n=200000
112 Correct 1085 ms 76952 KB n=200000
113 Correct 1132 ms 72288 KB n=200000
114 Correct 919 ms 69348 KB n=200000
115 Correct 1253 ms 70168 KB n=200000
116 Correct 828 ms 69088 KB n=200000
117 Correct 1068 ms 77064 KB n=200000
118 Correct 1193 ms 71060 KB n=200000
119 Correct 795 ms 69088 KB n=200000
120 Correct 973 ms 77484 KB n=200000
121 Correct 1014 ms 77528 KB n=200000
122 Correct 982 ms 78188 KB n=200000
123 Correct 633 ms 69748 KB n=200000
124 Correct 275 ms 38892 KB n=25264