oj.uz

Submission #878106

# Submission time Handle Problem Language Result Execution time Memory
878106 2023-11-24T05:33:19 Z TAhmed33 Tourism (JOI23_tourism) C++
28 / 100
 5000 ms 77664 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 25;
int in[MAXN], out[MAXN], depth[MAXN];
pair <int, int> sparse[__lg(MAXN)][MAXN];
vector <int> adj[MAXN];
int n, m, q;
int cnt = 0;
void dfs (int pos, int par, int dep = 1) {
	depth[pos] = dep;
	sparse[0][++cnt] = {dep, pos};
	assert(cnt < MAXN);
	in[pos] = cnt;
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos, dep + 1);
			sparse[0][++cnt] = {dep, pos};
			assert(cnt < MAXN);
		}
	}
	out[pos] = dep;
}
int query (int l, int r) {
	if (l > r) swap(l, r);
	if (l == r) return sparse[0][l].second;
	int x = __lg(r - l + 1);
	return min(sparse[x][l], sparse[x][r - (1 << x) + 1]).second;
}
int arr[MAXN];
int main () {
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, -1);
	for (int i = 1; i <= __lg(cnt); i++) {
		for (int j = 1; j <= cnt; j++) {
			sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
		}
	}
	for (int i = 1; i <= m; i++) cin >> arr[i];
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		vector <int> g;
		for (int j = l; j <= r; j++) g.push_back(arr[j]);
		sort(g.begin(), g.end(), [&] (int a, int b) {
			return in[a] < in[b];
		});
		int ans = depth[g[0]], lca = g[0];
		for (int j = 1; j < (int)g.size(); j++) {
			ans += depth[g[j]] - depth[query(in[g[j]], in[g[j - 1]])];
			lca = query(in[lca], in[g[j]]);
		}
		ans -= depth[lca]; ans++;
		cout << ans << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 4 ms 24920 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 9 ms 35164 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 6 ms 35280 KB Output is correct
7 Correct 6 ms 35164 KB Output is correct
8 Correct 6 ms 37464 KB Output is correct
9 Correct 9 ms 37208 KB Output is correct
10 Correct 8 ms 37208 KB Output is correct
11 Correct 9 ms 37212 KB Output is correct
12 Correct 10 ms 37208 KB Output is correct
13 Correct 10 ms 37208 KB Output is correct
14 Correct 10 ms 37212 KB Output is correct
15 Correct 8 ms 37212 KB Output is correct
16 Correct 7 ms 37208 KB Output is correct
17 Correct 7 ms 37212 KB Output is correct
18 Correct 7 ms 37212 KB Output is correct
19 Correct 7 ms 37212 KB Output is correct
20 Correct 8 ms 37364 KB Output is correct
21 Correct 8 ms 37328 KB Output is correct
22 Correct 7 ms 37212 KB Output is correct
23 Correct 7 ms 37304 KB Output is correct
24 Correct 7 ms 37208 KB Output is correct
25 Correct 7 ms 37336 KB Output is correct
26 Correct 7 ms 37212 KB Output is correct
27 Correct 5 ms 18896 KB Output is correct
28 Correct 6 ms 37212 KB Output is correct
29 Correct 6 ms 37212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 4 ms 24920 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 9 ms 35164 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 6 ms 35280 KB Output is correct
7 Correct 6 ms 35164 KB Output is correct
8 Correct 6 ms 37464 KB Output is correct
9 Correct 9 ms 37208 KB Output is correct
10 Correct 8 ms 37208 KB Output is correct
11 Correct 9 ms 37212 KB Output is correct
12 Correct 10 ms 37208 KB Output is correct
13 Correct 10 ms 37208 KB Output is correct
14 Correct 10 ms 37212 KB Output is correct
15 Correct 8 ms 37212 KB Output is correct
16 Correct 7 ms 37208 KB Output is correct
17 Correct 7 ms 37212 KB Output is correct
18 Correct 7 ms 37212 KB Output is correct
19 Correct 7 ms 37212 KB Output is correct
20 Correct 8 ms 37364 KB Output is correct
21 Correct 8 ms 37328 KB Output is correct
22 Correct 7 ms 37212 KB Output is correct
23 Correct 7 ms 37304 KB Output is correct
24 Correct 7 ms 37208 KB Output is correct
25 Correct 7 ms 37336 KB Output is correct
26 Correct 7 ms 37212 KB Output is correct
27 Correct 5 ms 18896 KB Output is correct
28 Correct 6 ms 37212 KB Output is correct
29 Correct 6 ms 37212 KB Output is correct
30 Correct 54 ms 41564 KB Output is correct
31 Correct 64 ms 41568 KB Output is correct
32 Correct 90 ms 43612 KB Output is correct
33 Correct 90 ms 43612 KB Output is correct
34 Correct 88 ms 43828 KB Output is correct
35 Correct 257 ms 43612 KB Output is correct
36 Correct 260 ms 43864 KB Output is correct
37 Correct 255 ms 43612 KB Output is correct
38 Correct 92 ms 43612 KB Output is correct
39 Correct 92 ms 43856 KB Output is correct
40 Correct 89 ms 43608 KB Output is correct
41 Correct 261 ms 43608 KB Output is correct
42 Correct 288 ms 43788 KB Output is correct
43 Correct 259 ms 43612 KB Output is correct
44 Correct 89 ms 43608 KB Output is correct
45 Correct 94 ms 43688 KB Output is correct
46 Correct 104 ms 43612 KB Output is correct
47 Correct 260 ms 43696 KB Output is correct
48 Correct 264 ms 43676 KB Output is correct
49 Correct 273 ms 43608 KB Output is correct
50 Correct 84 ms 43612 KB Output is correct
51 Correct 88 ms 43612 KB Output is correct
52 Correct 88 ms 43612 KB Output is correct
53 Correct 84 ms 43608 KB Output is correct
54 Correct 89 ms 43676 KB Output is correct
55 Correct 85 ms 43656 KB Output is correct
56 Correct 21 ms 19032 KB Output is correct
57 Correct 10 ms 43612 KB Output is correct
58 Correct 12 ms 43452 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 21 ms 19032 KB Output is correct
4 Execution timed out 5035 ms 74492 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 61 ms 68752 KB Output is correct
3 Correct 78 ms 71000 KB Output is correct
4 Correct 73 ms 75316 KB Output is correct
5 Correct 103 ms 77272 KB Output is correct
6 Correct 99 ms 76856 KB Output is correct
7 Correct 113 ms 76952 KB Output is correct
8 Correct 101 ms 76708 KB Output is correct
9 Correct 97 ms 76688 KB Output is correct
10 Correct 98 ms 76568 KB Output is correct
11 Correct 111 ms 76840 KB Output is correct
12 Correct 103 ms 76628 KB Output is correct
13 Correct 112 ms 76824 KB Output is correct
14 Correct 147 ms 76884 KB Output is correct
15 Correct 261 ms 77500 KB Output is correct
16 Correct 118 ms 77236 KB Output is correct
17 Correct 115 ms 77136 KB Output is correct
18 Correct 116 ms 77140 KB Output is correct
19 Correct 124 ms 77240 KB Output is correct
20 Correct 98 ms 77156 KB Output is correct
21 Correct 95 ms 76900 KB Output is correct
22 Correct 99 ms 76884 KB Output is correct
23 Correct 95 ms 76700 KB Output is correct
24 Correct 95 ms 76628 KB Output is correct
25 Correct 97 ms 76600 KB Output is correct
26 Correct 103 ms 76880 KB Output is correct
27 Correct 96 ms 76628 KB Output is correct
28 Correct 97 ms 76628 KB Output is correct
29 Correct 101 ms 76624 KB Output is correct
30 Correct 105 ms 76628 KB Output is correct
31 Correct 111 ms 77000 KB Output is correct
32 Correct 127 ms 77016 KB Output is correct
33 Correct 178 ms 76888 KB Output is correct
34 Correct 249 ms 77664 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 20 ms 18780 KB Output is correct
4 Execution timed out 5050 ms 70044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 4 ms 24920 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 9 ms 35164 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 6 ms 35280 KB Output is correct
7 Correct 6 ms 35164 KB Output is correct
8 Correct 6 ms 37464 KB Output is correct
9 Correct 9 ms 37208 KB Output is correct
10 Correct 8 ms 37208 KB Output is correct
11 Correct 9 ms 37212 KB Output is correct
12 Correct 10 ms 37208 KB Output is correct
13 Correct 10 ms 37208 KB Output is correct
14 Correct 10 ms 37212 KB Output is correct
15 Correct 8 ms 37212 KB Output is correct
16 Correct 7 ms 37208 KB Output is correct
17 Correct 7 ms 37212 KB Output is correct
18 Correct 7 ms 37212 KB Output is correct
19 Correct 7 ms 37212 KB Output is correct
20 Correct 8 ms 37364 KB Output is correct
21 Correct 8 ms 37328 KB Output is correct
22 Correct 7 ms 37212 KB Output is correct
23 Correct 7 ms 37304 KB Output is correct
24 Correct 7 ms 37208 KB Output is correct
25 Correct 7 ms 37336 KB Output is correct
26 Correct 7 ms 37212 KB Output is correct
27 Correct 5 ms 18896 KB Output is correct
28 Correct 6 ms 37212 KB Output is correct
29 Correct 6 ms 37212 KB Output is correct
30 Correct 54 ms 41564 KB Output is correct
31 Correct 64 ms 41568 KB Output is correct
32 Correct 90 ms 43612 KB Output is correct
33 Correct 90 ms 43612 KB Output is correct
34 Correct 88 ms 43828 KB Output is correct
35 Correct 257 ms 43612 KB Output is correct
36 Correct 260 ms 43864 KB Output is correct
37 Correct 255 ms 43612 KB Output is correct
38 Correct 92 ms 43612 KB Output is correct
39 Correct 92 ms 43856 KB Output is correct
40 Correct 89 ms 43608 KB Output is correct
41 Correct 261 ms 43608 KB Output is correct
42 Correct 288 ms 43788 KB Output is correct
43 Correct 259 ms 43612 KB Output is correct
44 Correct 89 ms 43608 KB Output is correct
45 Correct 94 ms 43688 KB Output is correct
46 Correct 104 ms 43612 KB Output is correct
47 Correct 260 ms 43696 KB Output is correct
48 Correct 264 ms 43676 KB Output is correct
49 Correct 273 ms 43608 KB Output is correct
50 Correct 84 ms 43612 KB Output is correct
51 Correct 88 ms 43612 KB Output is correct
52 Correct 88 ms 43612 KB Output is correct
53 Correct 84 ms 43608 KB Output is correct
54 Correct 89 ms 43676 KB Output is correct
55 Correct 85 ms 43656 KB Output is correct
56 Correct 21 ms 19032 KB Output is correct
57 Correct 10 ms 43612 KB Output is correct
58 Correct 12 ms 43452 KB Output is correct
59 Correct 4 ms 24920 KB Output is correct
60 Correct 4 ms 18780 KB Output is correct
61 Correct 21 ms 19032 KB Output is correct
62 Execution timed out 5035 ms 74492 KB Time limit exceeded
63 Halted 0 ms 0 KB -