oj.uz

Submission #874722

# Submission time Handle Problem Language Result Execution time Memory
874722 2023-11-17T17:01:22 Z MinaRagy06 Tourism (JOI23_tourism) C++17
100 / 100
 1328 ms 100300 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

const int N = 100'005;
int n, m, q, bit[N];
void upd(int x, int v) {
	for (int i = x; i < m; i = i | (i + 1)) {
		bit[i] += v;
	}
}
void add(int l, int r, int v) {
	upd(l, v);
	if (r + 1 < m) {
		upd(r + 1, -v);
	}
}
int get(int r) {
	int ans = 0;
	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
		ans += bit[i];
	}
	return ans;
}
int anc[18][N], h[N], mp[N], mph[N], mxh[N], height;
vector<int> adj[N];
int nodes = 1;
void dfs(int i, int d, int x, int curd, int p, int realp) {
	h[x] = d;
	mxh[x] = max(mxh[x], curd);
	mp[i] = x;
	mph[i] = curd;
	height = max(height, d);
	if (curd == 0) {
		anc[0][x] = p;
		for (int j = 1; j < 18; j++) {
			anc[j][x] = anc[j - 1][anc[j - 1][x]];
		}
	}
	for (auto nxt : adj[i]) {
		if (nxt == realp) continue;
		if ((int)adj[i].size() > (2 - (i == 1))) {
			dfs(nxt, d + 1, ++nodes, 0, x, i);
		} else {
			dfs(nxt, d, x, curd + 1, p, i);
		}
	}
}
int sparse[18][N];
int getlca(int u, int v) {
	if (h[u] > h[v]) {
		swap(u, v);
	}
	if (v == 0) return u;
	if (h[u] != h[v]) {
		for (int j = 17; j >= 0; j--) {
			if (h[anc[j][v]] > h[u]) {
				v = anc[j][v];
			}
		}
		v = anc[0][v];
	}
	if (u != v) {
		for (int j = 17; j >= 0; j--) {
			if (anc[j][u] != anc[j][v]) {
				u = anc[j][u];
				v = anc[j][v];
			}
		}
		u = anc[0][u];
	}
	return u;
}
int query(int l, int r) {
	int lg = __lg(r - l + 1);
	return getlca(sparse[lg][l], sparse[lg][r - (1 << lg) + 1]);
}
stack<array<int, 2>> s[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 1, 0, 1, 1);
	int arr[m];
	for (int i = 0; i < m; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < m; i++) {
		sparse[0][i] = mp[arr[i]];
	}
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i + (1 << (j - 1)) < m; i++) {
			sparse[j][i] = getlca(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
		}
	}
	vector<array<int, 3>> ask[m];
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		int lca = query(l, r);
		ask[r].push_back({l, i, h[lca]});
	}
	int ans[q]{};
	array<int, 2> a[m];
	for (int i = 0; i < m; i++) {
		a[i][0] = mp[arr[i]];
		a[i][1] = mph[arr[i]];
	}
	for (int j = height; j >= 0; j--) {
		memset(bit, 0, sizeof bit);
		for (int i = 0; i <= n; i++) {
			while (s[i].size()) s[i].pop();
			s[i].push({(int)1e9, -1});
		}
		for (int r = 0; r < m; r++) {
			auto &[cura, curh] = a[r];
			if (j > h[cura]) goto askl;
			add(s[cura].top()[1] + 1, r, curh + 1);
			while (curh >= s[cura].top()[0]) {
				array<int, 2> lst = s[cura].top();
				s[cura].pop();
				add(s[cura].top()[1] + 1, lst[1], curh - lst[0]);
			}
			s[cura].push({curh, r});
			cura = anc[0][cura];
			curh = mxh[cura];
askl:
			for (auto &[l, idx, mnh] : ask[r]) {
				if (j < mnh) continue;
				int v = get(l);
				ans[idx] += v;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		a[i][0] = mp[arr[i]];
		a[i][1] = mph[arr[i]];
	}
	for (int j = height; j >= 0; j--) {
		memset(bit, 0, sizeof bit);
		for (int i = 0; i <= n; i++) {
			while (s[i].size()) s[i].pop();
			s[i].push({(int)-1e9, -1});
		}
		for (int r = 0; r < m; r++) {
			auto &[cura, curh] = a[r];
			if (j > h[cura]) goto askl2;
			add(s[cura].top()[1] + 1, r, curh);
			while (curh <= s[cura].top()[0]) {
				array<int, 2> lst = s[cura].top();
				s[cura].pop();
				add(s[cura].top()[1] + 1, lst[1], curh - lst[0]);
			}
			s[cura].push({curh, r});
			cura = anc[0][cura];
			curh = mxh[cura];
askl2:
			for (auto &[l, idx, mnh] : ask[r]) {
				if (j != mnh) continue;
				int v = get(l);
				ans[idx] -= v;
			}
		}
	}
	for (auto i : ans) {
		cout << i << '\n';
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 81232 KB Output is correct
2 Correct 35 ms 80980 KB Output is correct
3 Correct 35 ms 80988 KB Output is correct
4 Correct 38 ms 83036 KB Output is correct
5 Correct 38 ms 83036 KB Output is correct
6 Correct 37 ms 83036 KB Output is correct
7 Correct 38 ms 82952 KB Output is correct
8 Correct 38 ms 83036 KB Output is correct
9 Correct 38 ms 82880 KB Output is correct
10 Correct 38 ms 83028 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 38 ms 83288 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 82868 KB Output is correct
15 Correct 37 ms 83028 KB Output is correct
16 Correct 37 ms 83032 KB Output is correct
17 Correct 38 ms 82948 KB Output is correct
18 Correct 37 ms 83024 KB Output is correct
19 Correct 37 ms 83028 KB Output is correct
20 Correct 37 ms 83032 KB Output is correct
21 Correct 37 ms 83036 KB Output is correct
22 Correct 38 ms 83012 KB Output is correct
23 Correct 36 ms 83036 KB Output is correct
24 Correct 37 ms 82968 KB Output is correct
25 Correct 36 ms 83036 KB Output is correct
26 Correct 42 ms 83144 KB Output is correct
27 Correct 36 ms 83056 KB Output is correct
28 Correct 36 ms 78936 KB Output is correct
29 Correct 39 ms 83028 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 81232 KB Output is correct
2 Correct 35 ms 80980 KB Output is correct
3 Correct 35 ms 80988 KB Output is correct
4 Correct 38 ms 83036 KB Output is correct
5 Correct 38 ms 83036 KB Output is correct
6 Correct 37 ms 83036 KB Output is correct
7 Correct 38 ms 82952 KB Output is correct
8 Correct 38 ms 83036 KB Output is correct
9 Correct 38 ms 82880 KB Output is correct
10 Correct 38 ms 83028 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 38 ms 83288 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 82868 KB Output is correct
15 Correct 37 ms 83028 KB Output is correct
16 Correct 37 ms 83032 KB Output is correct
17 Correct 38 ms 82948 KB Output is correct
18 Correct 37 ms 83024 KB Output is correct
19 Correct 37 ms 83028 KB Output is correct
20 Correct 37 ms 83032 KB Output is correct
21 Correct 37 ms 83036 KB Output is correct
22 Correct 38 ms 83012 KB Output is correct
23 Correct 36 ms 83036 KB Output is correct
24 Correct 37 ms 82968 KB Output is correct
25 Correct 36 ms 83036 KB Output is correct
26 Correct 42 ms 83144 KB Output is correct
27 Correct 36 ms 83056 KB Output is correct
28 Correct 36 ms 78936 KB Output is correct
29 Correct 39 ms 83028 KB Output is correct
30 Correct 40 ms 83228 KB Output is correct
31 Correct 41 ms 83120 KB Output is correct
32 Correct 42 ms 83292 KB Output is correct
33 Correct 44 ms 83280 KB Output is correct
34 Correct 41 ms 83280 KB Output is correct
35 Correct 43 ms 83284 KB Output is correct
36 Correct 42 ms 83280 KB Output is correct
37 Correct 42 ms 83208 KB Output is correct
38 Correct 38 ms 83288 KB Output is correct
39 Correct 38 ms 83120 KB Output is correct
40 Correct 43 ms 83596 KB Output is correct
41 Correct 38 ms 83292 KB Output is correct
42 Correct 38 ms 83220 KB Output is correct
43 Correct 38 ms 83220 KB Output is correct
44 Correct 42 ms 83292 KB Output is correct
45 Correct 40 ms 83020 KB Output is correct
46 Correct 42 ms 83292 KB Output is correct
47 Correct 41 ms 83280 KB Output is correct
48 Correct 41 ms 83292 KB Output is correct
49 Correct 40 ms 83028 KB Output is correct
50 Correct 39 ms 83264 KB Output is correct
51 Correct 37 ms 83288 KB Output is correct
52 Correct 37 ms 83180 KB Output is correct
53 Correct 37 ms 83292 KB Output is correct
54 Correct 39 ms 83452 KB Output is correct
55 Correct 39 ms 83168 KB Output is correct
56 Correct 38 ms 83040 KB Output is correct
57 Correct 38 ms 78952 KB Output is correct
58 Correct 41 ms 83296 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80980 KB Output is correct
2 Correct 36 ms 83032 KB Output is correct
3 Correct 37 ms 83032 KB Output is correct
4 Correct 101 ms 93292 KB Output is correct
5 Correct 97 ms 95628 KB Output is correct
6 Correct 97 ms 96740 KB Output is correct
7 Correct 121 ms 98852 KB Output is correct
8 Correct 133 ms 99004 KB Output is correct
9 Correct 123 ms 98760 KB Output is correct
10 Correct 124 ms 98872 KB Output is correct
11 Correct 118 ms 98772 KB Output is correct
12 Correct 115 ms 98532 KB Output is correct
13 Correct 106 ms 98468 KB Output is correct
14 Correct 110 ms 98640 KB Output is correct
15 Correct 76 ms 91232 KB Output is correct
16 Correct 127 ms 98848 KB Output is correct
17 Correct 91 ms 91412 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80976 KB Output is correct
2 Correct 237 ms 89224 KB Output is correct
3 Correct 390 ms 90448 KB Output is correct
4 Correct 330 ms 90008 KB Output is correct
5 Correct 469 ms 92692 KB Output is correct
6 Correct 581 ms 92636 KB Output is correct
7 Correct 486 ms 92504 KB Output is correct
8 Correct 500 ms 92824 KB Output is correct
9 Correct 491 ms 92500 KB Output is correct
10 Correct 565 ms 92648 KB Output is correct
11 Correct 535 ms 92756 KB Output is correct
12 Correct 614 ms 92732 KB Output is correct
13 Correct 501 ms 92980 KB Output is correct
14 Correct 538 ms 93780 KB Output is correct
15 Correct 647 ms 96152 KB Output is correct
16 Correct 582 ms 92788 KB Output is correct
17 Correct 545 ms 93012 KB Output is correct
18 Correct 539 ms 92984 KB Output is correct
19 Correct 873 ms 91796 KB Output is correct
20 Correct 726 ms 91800 KB Output is correct
21 Correct 682 ms 91728 KB Output is correct
22 Correct 840 ms 91800 KB Output is correct
23 Correct 829 ms 91800 KB Output is correct
24 Correct 805 ms 91620 KB Output is correct
25 Correct 839 ms 91800 KB Output is correct
26 Correct 862 ms 91804 KB Output is correct
27 Correct 811 ms 91816 KB Output is correct
28 Correct 781 ms 91988 KB Output is correct
29 Correct 818 ms 91868 KB Output is correct
30 Correct 842 ms 91984 KB Output is correct
31 Correct 835 ms 92152 KB Output is correct
32 Correct 816 ms 92508 KB Output is correct
33 Correct 730 ms 93556 KB Output is correct
34 Correct 1045 ms 95324 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80988 KB Output is correct
2 Correct 39 ms 82976 KB Output is correct
3 Correct 37 ms 83284 KB Output is correct
4 Correct 429 ms 93504 KB Output is correct
5 Correct 450 ms 93568 KB Output is correct
6 Correct 544 ms 95056 KB Output is correct
7 Correct 580 ms 96092 KB Output is correct
8 Correct 588 ms 96084 KB Output is correct
9 Correct 563 ms 95988 KB Output is correct
10 Correct 581 ms 95780 KB Output is correct
11 Correct 580 ms 96084 KB Output is correct
12 Correct 585 ms 95824 KB Output is correct
13 Correct 575 ms 95936 KB Output is correct
14 Correct 89 ms 91220 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 81232 KB Output is correct
2 Correct 35 ms 80980 KB Output is correct
3 Correct 35 ms 80988 KB Output is correct
4 Correct 38 ms 83036 KB Output is correct
5 Correct 38 ms 83036 KB Output is correct
6 Correct 37 ms 83036 KB Output is correct
7 Correct 38 ms 82952 KB Output is correct
8 Correct 38 ms 83036 KB Output is correct
9 Correct 38 ms 82880 KB Output is correct
10 Correct 38 ms 83028 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 38 ms 83288 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 82868 KB Output is correct
15 Correct 37 ms 83028 KB Output is correct
16 Correct 37 ms 83032 KB Output is correct
17 Correct 38 ms 82948 KB Output is correct
18 Correct 37 ms 83024 KB Output is correct
19 Correct 37 ms 83028 KB Output is correct
20 Correct 37 ms 83032 KB Output is correct
21 Correct 37 ms 83036 KB Output is correct
22 Correct 38 ms 83012 KB Output is correct
23 Correct 36 ms 83036 KB Output is correct
24 Correct 37 ms 82968 KB Output is correct
25 Correct 36 ms 83036 KB Output is correct
26 Correct 42 ms 83144 KB Output is correct
27 Correct 36 ms 83056 KB Output is correct
28 Correct 36 ms 78936 KB Output is correct
29 Correct 39 ms 83028 KB Output is correct
30 Correct 40 ms 83228 KB Output is correct
31 Correct 41 ms 83120 KB Output is correct
32 Correct 42 ms 83292 KB Output is correct
33 Correct 44 ms 83280 KB Output is correct
34 Correct 41 ms 83280 KB Output is correct
35 Correct 43 ms 83284 KB Output is correct
36 Correct 42 ms 83280 KB Output is correct
37 Correct 42 ms 83208 KB Output is correct
38 Correct 38 ms 83288 KB Output is correct
39 Correct 38 ms 83120 KB Output is correct
40 Correct 43 ms 83596 KB Output is correct
41 Correct 38 ms 83292 KB Output is correct
42 Correct 38 ms 83220 KB Output is correct
43 Correct 38 ms 83220 KB Output is correct
44 Correct 42 ms 83292 KB Output is correct
45 Correct 40 ms 83020 KB Output is correct
46 Correct 42 ms 83292 KB Output is correct
47 Correct 41 ms 83280 KB Output is correct
48 Correct 41 ms 83292 KB Output is correct
49 Correct 40 ms 83028 KB Output is correct
50 Correct 39 ms 83264 KB Output is correct
51 Correct 37 ms 83288 KB Output is correct
52 Correct 37 ms 83180 KB Output is correct
53 Correct 37 ms 83292 KB Output is correct
54 Correct 39 ms 83452 KB Output is correct
55 Correct 39 ms 83168 KB Output is correct
56 Correct 38 ms 83040 KB Output is correct
57 Correct 38 ms 78952 KB Output is correct
58 Correct 41 ms 83296 KB Output is correct
59 Correct 36 ms 80980 KB Output is correct
60 Correct 36 ms 83032 KB Output is correct
61 Correct 37 ms 83032 KB Output is correct
62 Correct 101 ms 93292 KB Output is correct
63 Correct 97 ms 95628 KB Output is correct
64 Correct 97 ms 96740 KB Output is correct
65 Correct 121 ms 98852 KB Output is correct
66 Correct 133 ms 99004 KB Output is correct
67 Correct 123 ms 98760 KB Output is correct
68 Correct 124 ms 98872 KB Output is correct
69 Correct 118 ms 98772 KB Output is correct
70 Correct 115 ms 98532 KB Output is correct
71 Correct 106 ms 98468 KB Output is correct
72 Correct 110 ms 98640 KB Output is correct
73 Correct 76 ms 91232 KB Output is correct
74 Correct 127 ms 98848 KB Output is correct
75 Correct 91 ms 91412 KB Output is correct
76 Correct 37 ms 80976 KB Output is correct
77 Correct 237 ms 89224 KB Output is correct
78 Correct 390 ms 90448 KB Output is correct
79 Correct 330 ms 90008 KB Output is correct
80 Correct 469 ms 92692 KB Output is correct
81 Correct 581 ms 92636 KB Output is correct
82 Correct 486 ms 92504 KB Output is correct
83 Correct 500 ms 92824 KB Output is correct
84 Correct 491 ms 92500 KB Output is correct
85 Correct 565 ms 92648 KB Output is correct
86 Correct 535 ms 92756 KB Output is correct
87 Correct 614 ms 92732 KB Output is correct
88 Correct 501 ms 92980 KB Output is correct
89 Correct 538 ms 93780 KB Output is correct
90 Correct 647 ms 96152 KB Output is correct
91 Correct 582 ms 92788 KB Output is correct
92 Correct 545 ms 93012 KB Output is correct
93 Correct 539 ms 92984 KB Output is correct
94 Correct 873 ms 91796 KB Output is correct
95 Correct 726 ms 91800 KB Output is correct
96 Correct 682 ms 91728 KB Output is correct
97 Correct 840 ms 91800 KB Output is correct
98 Correct 829 ms 91800 KB Output is correct
99 Correct 805 ms 91620 KB Output is correct
100 Correct 839 ms 91800 KB Output is correct
101 Correct 862 ms 91804 KB Output is correct
102 Correct 811 ms 91816 KB Output is correct
103 Correct 781 ms 91988 KB Output is correct
104 Correct 818 ms 91868 KB Output is correct
105 Correct 842 ms 91984 KB Output is correct
106 Correct 835 ms 92152 KB Output is correct
107 Correct 816 ms 92508 KB Output is correct
108 Correct 730 ms 93556 KB Output is correct
109 Correct 1045 ms 95324 KB Output is correct
110 Correct 37 ms 80988 KB Output is correct
111 Correct 39 ms 82976 KB Output is correct
112 Correct 37 ms 83284 KB Output is correct
113 Correct 429 ms 93504 KB Output is correct
114 Correct 450 ms 93568 KB Output is correct
115 Correct 544 ms 95056 KB Output is correct
116 Correct 580 ms 96092 KB Output is correct
117 Correct 588 ms 96084 KB Output is correct
118 Correct 563 ms 95988 KB Output is correct
119 Correct 581 ms 95780 KB Output is correct
120 Correct 580 ms 96084 KB Output is correct
121 Correct 585 ms 95824 KB Output is correct
122 Correct 575 ms 95936 KB Output is correct
123 Correct 89 ms 91220 KB Output is correct
124 Correct 674 ms 95024 KB Output is correct
125 Correct 546 ms 92960 KB Output is correct
126 Correct 709 ms 95716 KB Output is correct
127 Correct 772 ms 95708 KB Output is correct
128 Correct 798 ms 95828 KB Output is correct
129 Correct 828 ms 95704 KB Output is correct
130 Correct 749 ms 95708 KB Output is correct
131 Correct 157 ms 98900 KB Output is correct
132 Correct 169 ms 100300 KB Output is correct
133 Correct 164 ms 95568 KB Output is correct
134 Correct 1182 ms 94876 KB Output is correct
135 Correct 1328 ms 94880 KB Output is correct
136 Correct 1012 ms 95060 KB Output is correct
137 Correct 178 ms 96292 KB Output is correct
138 Correct 174 ms 96292 KB Output is correct
139 Correct 189 ms 96296 KB Output is correct
140 Correct 181 ms 96144 KB Output is correct
141 Correct 188 ms 96196 KB Output is correct
142 Correct 189 ms 96200 KB Output is correct
143 Correct 209 ms 84668 KB Output is correct
144 Correct 793 ms 95384 KB Output is correct