oj.uz

Submission #797380

# Submission time Handle Problem Language Result Execution time Memory
797380 2023-07-29T10:12:05 Z kingfran1907 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1385 ms 80932 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int logo = 20;

int n, m, q;
vector< int > graph[maxn];
int dp[logo + 10][maxn];
int dis[maxn];
int niz[maxn];
map< int, set< pair<int, int> > > qs;

void dfs(int x, int parr) {
	dp[0][x] = parr;
	dis[x] = 1 + dis[parr];
	
	for (int tren : graph[x]) {
		if (tren != parr) dfs(tren, x);
	}
}

int lif(int x, int val) {
	for (int i = 0; i < logo; i++)
		if (val & (1 << i)) x = dp[i][x];
	return x;
}

int lca(int a, int b) {
	if (dis[a] > dis[b]) a = lif(a, dis[a] - dis[b]);
	else b = lif(b, dis[b] - dis[a]);
	if (a == b) return a;
	
	for (int i = logo - 1; i >= 0; i--) {
		if (dp[i][a] != dp[i][b]) {
			a = dp[i][a];
			b = dp[i][b];
		}
	}
	return dp[0][a];
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	dfs(1, 0);
	for (int i = 1; i < logo; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
	
	for (int i = 0; i < m; i++) {
		scanf("%d", niz+i);
		qs[niz[i]].insert({i, i});
		if (i > 0) qs[lca(niz[i - 1], niz[i])].insert({i - 1, i});
	}
	
	while (q--) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			int x, v;
			scanf("%d%d", &x, &v); x--;
			qs[niz[x]].erase({x, x});
			if (x > 0) qs[lca(niz[x - 1], niz[x])].erase({x - 1, x});
			if (x < m - 1) qs[lca(niz[x], niz[x + 1])].erase({x, x + 1});
			
			niz[x] = v;
			qs[niz[x]].insert({x, x});
			if (x > 0) qs[lca(niz[x - 1], niz[x])].insert({x - 1, x});
			if (x < m - 1) qs[lca(niz[x], niz[x + 1])].insert({x, x + 1});
		} else {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v); l--, r--;
			auto iter = qs[v].lower_bound({l, l});
			if (iter == qs[v].end() || iter->second > r) printf("-1 -1\n");
			else printf("%d %d\n", iter->first + 1, iter->second + 1);
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
treearray.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf("%d%d", &x, &v); x--;
      |    ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d%d%d", &l, &r, &v); l--, r--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB n=5
2 Correct 2 ms 5076 KB n=100
3 Correct 3 ms 5076 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5076 KB n=100
6 Correct 3 ms 5076 KB n=100
7 Correct 3 ms 5136 KB n=100
8 Correct 3 ms 5136 KB n=100
9 Correct 3 ms 5076 KB n=100
10 Correct 3 ms 5132 KB n=100
11 Correct 3 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5100 KB n=100
14 Correct 4 ms 5120 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 4 ms 5076 KB n=100
17 Correct 3 ms 5076 KB n=100
18 Correct 2 ms 5132 KB n=100
19 Correct 3 ms 5076 KB n=100
20 Correct 3 ms 5132 KB n=100
21 Correct 3 ms 5132 KB n=100
22 Correct 3 ms 5132 KB n=100
23 Correct 2 ms 5076 KB n=100
24 Correct 3 ms 5076 KB n=100
25 Correct 2 ms 5076 KB n=100
26 Correct 3 ms 5076 KB n=12
27 Correct 3 ms 5076 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 3 ms 5280 KB n=500
30 Correct 3 ms 5204 KB n=500
31 Correct 3 ms 5204 KB n=500
32 Correct 3 ms 5268 KB n=500
33 Correct 3 ms 5272 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 3 ms 5204 KB n=500
36 Correct 3 ms 5260 KB n=500
37 Correct 3 ms 5204 KB n=500
38 Correct 3 ms 5204 KB n=500
39 Correct 3 ms 5276 KB n=500
40 Correct 3 ms 5276 KB n=500
41 Correct 3 ms 5204 KB n=500
42 Correct 4 ms 5204 KB n=500
43 Correct 3 ms 5204 KB n=500
44 Correct 3 ms 5276 KB n=500
45 Correct 3 ms 5204 KB n=500
46 Correct 4 ms 5268 KB n=500
47 Correct 3 ms 5272 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 3 ms 5204 KB n=500
50 Correct 3 ms 5204 KB n=500
51 Correct 3 ms 5204 KB n=500
52 Correct 3 ms 5204 KB n=500
53 Correct 3 ms 5204 KB n=500
54 Correct 3 ms 5204 KB n=500
55 Correct 3 ms 5204 KB n=278
56 Correct 3 ms 5204 KB n=500
57 Correct 3 ms 5204 KB n=500
58 Correct 3 ms 5184 KB n=500
59 Correct 5 ms 5716 KB n=2000
60 Correct 5 ms 5716 KB n=2000
61 Correct 6 ms 5716 KB n=2000
62 Correct 6 ms 5716 KB n=2000
63 Correct 5 ms 5716 KB n=2000
64 Correct 6 ms 5756 KB n=2000
65 Correct 5 ms 5752 KB n=2000
66 Correct 6 ms 5716 KB n=2000
67 Correct 6 ms 5716 KB n=2000
68 Correct 6 ms 5716 KB n=2000
69 Correct 5 ms 5660 KB n=2000
70 Correct 4 ms 5716 KB n=2000
71 Correct 5 ms 5716 KB n=2000
72 Correct 4 ms 5656 KB n=2000
73 Correct 4 ms 5716 KB n=2000
74 Correct 5 ms 5716 KB n=1844
75 Correct 5 ms 5656 KB n=2000
76 Correct 6 ms 5648 KB n=2000
77 Correct 5 ms 5716 KB n=2000
78 Correct 6 ms 5656 KB n=2000
79 Correct 5 ms 5716 KB n=2000
80 Correct 5 ms 5716 KB n=2000
81 Correct 6 ms 5784 KB n=2000
82 Correct 5 ms 5716 KB n=2000
83 Correct 6 ms 5716 KB n=2000
84 Correct 7 ms 5716 KB n=2000
85 Correct 6 ms 5716 KB n=2000
86 Correct 6 ms 5764 KB n=2000
87 Correct 5 ms 5656 KB n=2000
88 Correct 5 ms 5844 KB n=2000
89 Correct 8 ms 5784 KB n=2000
90 Correct 6 ms 5784 KB n=2000
91 Correct 5 ms 5716 KB n=2000
92 Correct 1049 ms 70320 KB n=200000
93 Correct 1271 ms 75720 KB n=200000
94 Correct 1158 ms 78776 KB n=200000
95 Correct 1042 ms 70080 KB n=200000
96 Correct 1024 ms 70276 KB n=200000
97 Correct 1295 ms 74788 KB n=200000
98 Correct 1008 ms 70232 KB n=200000
99 Correct 1164 ms 70420 KB n=200000
100 Correct 1006 ms 70176 KB n=200000
101 Correct 1162 ms 79860 KB n=200000
102 Correct 456 ms 68556 KB n=200000
103 Correct 461 ms 68584 KB n=200000
104 Correct 459 ms 68584 KB n=200000
105 Correct 463 ms 69076 KB n=200000
106 Correct 453 ms 69064 KB n=200000
107 Correct 475 ms 69044 KB n=200000
108 Correct 1065 ms 70152 KB n=200000
109 Correct 1025 ms 70208 KB n=200000
110 Correct 1029 ms 70356 KB n=200000
111 Correct 895 ms 66948 KB n=200000
112 Correct 1164 ms 78884 KB n=200000
113 Correct 1267 ms 74444 KB n=200000
114 Correct 878 ms 66964 KB n=200000
115 Correct 1385 ms 72028 KB n=200000
116 Correct 1000 ms 71928 KB n=200000
117 Correct 1168 ms 80932 KB n=200000
118 Correct 1369 ms 74988 KB n=200000
119 Correct 1056 ms 71864 KB n=200000
120 Correct 1047 ms 78860 KB n=200000
121 Correct 1305 ms 78844 KB n=200000
122 Correct 1343 ms 79132 KB n=200000
123 Correct 727 ms 68880 KB n=200000
124 Correct 265 ms 22356 KB n=25264