oj.uz

Submission #874720

# Submission time Handle Problem Language Result Execution time Memory
874720 2023-11-17T16:52:12 Z MinaRagy06 Tourism (JOI23_tourism) C++17
100 / 100
 1378 ms 103508 KB 
#include <bits/stdc++.h>
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 36 ms 80984 KB Output is correct
2 Correct 44 ms 80928 KB Output is correct
3 Correct 46 ms 80988 KB Output is correct
4 Correct 42 ms 83180 KB Output is correct
5 Correct 37 ms 83024 KB Output is correct
6 Correct 38 ms 82928 KB Output is correct
7 Correct 47 ms 83020 KB Output is correct
8 Correct 38 ms 83032 KB Output is correct
9 Correct 37 ms 83032 KB Output is correct
10 Correct 38 ms 83036 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 37 ms 83032 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 83036 KB Output is correct
15 Correct 38 ms 83024 KB Output is correct
16 Correct 40 ms 83152 KB Output is correct
17 Correct 42 ms 82940 KB Output is correct
18 Correct 47 ms 82924 KB Output is correct
19 Correct 38 ms 83028 KB Output is correct
20 Correct 38 ms 83028 KB Output is correct
21 Correct 36 ms 83116 KB Output is correct
22 Correct 37 ms 83028 KB Output is correct
23 Correct 37 ms 83024 KB Output is correct
24 Correct 39 ms 83028 KB Output is correct
25 Correct 37 ms 83024 KB Output is correct
26 Correct 48 ms 83120 KB Output is correct
27 Correct 38 ms 83032 KB Output is correct
28 Correct 36 ms 78928 KB Output is correct
29 Correct 38 ms 83088 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80984 KB Output is correct
2 Correct 44 ms 80928 KB Output is correct
3 Correct 46 ms 80988 KB Output is correct
4 Correct 42 ms 83180 KB Output is correct
5 Correct 37 ms 83024 KB Output is correct
6 Correct 38 ms 82928 KB Output is correct
7 Correct 47 ms 83020 KB Output is correct
8 Correct 38 ms 83032 KB Output is correct
9 Correct 37 ms 83032 KB Output is correct
10 Correct 38 ms 83036 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 37 ms 83032 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 83036 KB Output is correct
15 Correct 38 ms 83024 KB Output is correct
16 Correct 40 ms 83152 KB Output is correct
17 Correct 42 ms 82940 KB Output is correct
18 Correct 47 ms 82924 KB Output is correct
19 Correct 38 ms 83028 KB Output is correct
20 Correct 38 ms 83028 KB Output is correct
21 Correct 36 ms 83116 KB Output is correct
22 Correct 37 ms 83028 KB Output is correct
23 Correct 37 ms 83024 KB Output is correct
24 Correct 39 ms 83028 KB Output is correct
25 Correct 37 ms 83024 KB Output is correct
26 Correct 48 ms 83120 KB Output is correct
27 Correct 38 ms 83032 KB Output is correct
28 Correct 36 ms 78928 KB Output is correct
29 Correct 38 ms 83088 KB Output is correct
30 Correct 42 ms 83264 KB Output is correct
31 Correct 41 ms 83280 KB Output is correct
32 Correct 43 ms 83280 KB Output is correct
33 Correct 44 ms 83152 KB Output is correct
34 Correct 43 ms 83124 KB Output is correct
35 Correct 53 ms 83284 KB Output is correct
36 Correct 43 ms 83292 KB Output is correct
37 Correct 42 ms 83292 KB Output is correct
38 Correct 38 ms 83292 KB Output is correct
39 Correct 39 ms 83292 KB Output is correct
40 Correct 45 ms 83292 KB Output is correct
41 Correct 47 ms 83296 KB Output is correct
42 Correct 40 ms 83244 KB Output is correct
43 Correct 38 ms 83256 KB Output is correct
44 Correct 42 ms 83104 KB Output is correct
45 Correct 48 ms 83300 KB Output is correct
46 Correct 42 ms 83288 KB Output is correct
47 Correct 41 ms 83292 KB Output is correct
48 Correct 50 ms 83280 KB Output is correct
49 Correct 44 ms 83312 KB Output is correct
50 Correct 39 ms 83288 KB Output is correct
51 Correct 38 ms 83284 KB Output is correct
52 Correct 41 ms 83280 KB Output is correct
53 Correct 40 ms 83252 KB Output is correct
54 Correct 39 ms 83284 KB Output is correct
55 Correct 41 ms 83280 KB Output is correct
56 Correct 39 ms 83036 KB Output is correct
57 Correct 40 ms 78984 KB Output is correct
58 Correct 42 ms 83292 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 80972 KB Output is correct
2 Correct 37 ms 83048 KB Output is correct
3 Correct 38 ms 83036 KB Output is correct
4 Correct 99 ms 96192 KB Output is correct
5 Correct 93 ms 98896 KB Output is correct
6 Correct 104 ms 100504 KB Output is correct
7 Correct 129 ms 103248 KB Output is correct
8 Correct 127 ms 103264 KB Output is correct
9 Correct 124 ms 103508 KB Output is correct
10 Correct 135 ms 103132 KB Output is correct
11 Correct 141 ms 103200 KB Output is correct
12 Correct 110 ms 102740 KB Output is correct
13 Correct 115 ms 102616 KB Output is correct
14 Correct 123 ms 102744 KB Output is correct
15 Correct 80 ms 94408 KB Output is correct
16 Correct 119 ms 102740 KB Output is correct
17 Correct 91 ms 92756 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80940 KB Output is correct
2 Correct 249 ms 90180 KB Output is correct
3 Correct 389 ms 91728 KB Output is correct
4 Correct 368 ms 91884 KB Output is correct
5 Correct 475 ms 94292 KB Output is correct
6 Correct 593 ms 94168 KB Output is correct
7 Correct 510 ms 94548 KB Output is correct
8 Correct 535 ms 94544 KB Output is correct
9 Correct 512 ms 94292 KB Output is correct
10 Correct 576 ms 94380 KB Output is correct
11 Correct 544 ms 94544 KB Output is correct
12 Correct 677 ms 94292 KB Output is correct
13 Correct 510 ms 94832 KB Output is correct
14 Correct 545 ms 95824 KB Output is correct
15 Correct 667 ms 99224 KB Output is correct
16 Correct 638 ms 94804 KB Output is correct
17 Correct 546 ms 94832 KB Output is correct
18 Correct 567 ms 95060 KB Output is correct
19 Correct 933 ms 93532 KB Output is correct
20 Correct 771 ms 93532 KB Output is correct
21 Correct 699 ms 93584 KB Output is correct
22 Correct 870 ms 93532 KB Output is correct
23 Correct 848 ms 93528 KB Output is correct
24 Correct 813 ms 93776 KB Output is correct
25 Correct 857 ms 93536 KB Output is correct
26 Correct 846 ms 93776 KB Output is correct
27 Correct 853 ms 93780 KB Output is correct
28 Correct 779 ms 93576 KB Output is correct
29 Correct 846 ms 93616 KB Output is correct
30 Correct 846 ms 93772 KB Output is correct
31 Correct 809 ms 93996 KB Output is correct
32 Correct 789 ms 94472 KB Output is correct
33 Correct 740 ms 95828 KB Output is correct
34 Correct 1063 ms 98384 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 80980 KB Output is correct
2 Correct 38 ms 83036 KB Output is correct
3 Correct 37 ms 83192 KB Output is correct
4 Correct 477 ms 95576 KB Output is correct
5 Correct 441 ms 95572 KB Output is correct
6 Correct 555 ms 97624 KB Output is correct
7 Correct 605 ms 98748 KB Output is correct
8 Correct 614 ms 98940 KB Output is correct
9 Correct 597 ms 98640 KB Output is correct
10 Correct 581 ms 98756 KB Output is correct
11 Correct 609 ms 98760 KB Output is correct
12 Correct 620 ms 98864 KB Output is correct
13 Correct 588 ms 98752 KB Output is correct
14 Correct 88 ms 92748 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80984 KB Output is correct
2 Correct 44 ms 80928 KB Output is correct
3 Correct 46 ms 80988 KB Output is correct
4 Correct 42 ms 83180 KB Output is correct
5 Correct 37 ms 83024 KB Output is correct
6 Correct 38 ms 82928 KB Output is correct
7 Correct 47 ms 83020 KB Output is correct
8 Correct 38 ms 83032 KB Output is correct
9 Correct 37 ms 83032 KB Output is correct
10 Correct 38 ms 83036 KB Output is correct
11 Correct 38 ms 83028 KB Output is correct
12 Correct 37 ms 83032 KB Output is correct
13 Correct 38 ms 83028 KB Output is correct
14 Correct 37 ms 83036 KB Output is correct
15 Correct 38 ms 83024 KB Output is correct
16 Correct 40 ms 83152 KB Output is correct
17 Correct 42 ms 82940 KB Output is correct
18 Correct 47 ms 82924 KB Output is correct
19 Correct 38 ms 83028 KB Output is correct
20 Correct 38 ms 83028 KB Output is correct
21 Correct 36 ms 83116 KB Output is correct
22 Correct 37 ms 83028 KB Output is correct
23 Correct 37 ms 83024 KB Output is correct
24 Correct 39 ms 83028 KB Output is correct
25 Correct 37 ms 83024 KB Output is correct
26 Correct 48 ms 83120 KB Output is correct
27 Correct 38 ms 83032 KB Output is correct
28 Correct 36 ms 78928 KB Output is correct
29 Correct 38 ms 83088 KB Output is correct
30 Correct 42 ms 83264 KB Output is correct
31 Correct 41 ms 83280 KB Output is correct
32 Correct 43 ms 83280 KB Output is correct
33 Correct 44 ms 83152 KB Output is correct
34 Correct 43 ms 83124 KB Output is correct
35 Correct 53 ms 83284 KB Output is correct
36 Correct 43 ms 83292 KB Output is correct
37 Correct 42 ms 83292 KB Output is correct
38 Correct 38 ms 83292 KB Output is correct
39 Correct 39 ms 83292 KB Output is correct
40 Correct 45 ms 83292 KB Output is correct
41 Correct 47 ms 83296 KB Output is correct
42 Correct 40 ms 83244 KB Output is correct
43 Correct 38 ms 83256 KB Output is correct
44 Correct 42 ms 83104 KB Output is correct
45 Correct 48 ms 83300 KB Output is correct
46 Correct 42 ms 83288 KB Output is correct
47 Correct 41 ms 83292 KB Output is correct
48 Correct 50 ms 83280 KB Output is correct
49 Correct 44 ms 83312 KB Output is correct
50 Correct 39 ms 83288 KB Output is correct
51 Correct 38 ms 83284 KB Output is correct
52 Correct 41 ms 83280 KB Output is correct
53 Correct 40 ms 83252 KB Output is correct
54 Correct 39 ms 83284 KB Output is correct
55 Correct 41 ms 83280 KB Output is correct
56 Correct 39 ms 83036 KB Output is correct
57 Correct 40 ms 78984 KB Output is correct
58 Correct 42 ms 83292 KB Output is correct
59 Correct 45 ms 80972 KB Output is correct
60 Correct 37 ms 83048 KB Output is correct
61 Correct 38 ms 83036 KB Output is correct
62 Correct 99 ms 96192 KB Output is correct
63 Correct 93 ms 98896 KB Output is correct
64 Correct 104 ms 100504 KB Output is correct
65 Correct 129 ms 103248 KB Output is correct
66 Correct 127 ms 103264 KB Output is correct
67 Correct 124 ms 103508 KB Output is correct
68 Correct 135 ms 103132 KB Output is correct
69 Correct 141 ms 103200 KB Output is correct
70 Correct 110 ms 102740 KB Output is correct
71 Correct 115 ms 102616 KB Output is correct
72 Correct 123 ms 102744 KB Output is correct
73 Correct 80 ms 94408 KB Output is correct
74 Correct 119 ms 102740 KB Output is correct
75 Correct 91 ms 92756 KB Output is correct
76 Correct 40 ms 80940 KB Output is correct
77 Correct 249 ms 90180 KB Output is correct
78 Correct 389 ms 91728 KB Output is correct
79 Correct 368 ms 91884 KB Output is correct
80 Correct 475 ms 94292 KB Output is correct
81 Correct 593 ms 94168 KB Output is correct
82 Correct 510 ms 94548 KB Output is correct
83 Correct 535 ms 94544 KB Output is correct
84 Correct 512 ms 94292 KB Output is correct
85 Correct 576 ms 94380 KB Output is correct
86 Correct 544 ms 94544 KB Output is correct
87 Correct 677 ms 94292 KB Output is correct
88 Correct 510 ms 94832 KB Output is correct
89 Correct 545 ms 95824 KB Output is correct
90 Correct 667 ms 99224 KB Output is correct
91 Correct 638 ms 94804 KB Output is correct
92 Correct 546 ms 94832 KB Output is correct
93 Correct 567 ms 95060 KB Output is correct
94 Correct 933 ms 93532 KB Output is correct
95 Correct 771 ms 93532 KB Output is correct
96 Correct 699 ms 93584 KB Output is correct
97 Correct 870 ms 93532 KB Output is correct
98 Correct 848 ms 93528 KB Output is correct
99 Correct 813 ms 93776 KB Output is correct
100 Correct 857 ms 93536 KB Output is correct
101 Correct 846 ms 93776 KB Output is correct
102 Correct 853 ms 93780 KB Output is correct
103 Correct 779 ms 93576 KB Output is correct
104 Correct 846 ms 93616 KB Output is correct
105 Correct 846 ms 93772 KB Output is correct
106 Correct 809 ms 93996 KB Output is correct
107 Correct 789 ms 94472 KB Output is correct
108 Correct 740 ms 95828 KB Output is correct
109 Correct 1063 ms 98384 KB Output is correct
110 Correct 45 ms 80980 KB Output is correct
111 Correct 38 ms 83036 KB Output is correct
112 Correct 37 ms 83192 KB Output is correct
113 Correct 477 ms 95576 KB Output is correct
114 Correct 441 ms 95572 KB Output is correct
115 Correct 555 ms 97624 KB Output is correct
116 Correct 605 ms 98748 KB Output is correct
117 Correct 614 ms 98940 KB Output is correct
118 Correct 597 ms 98640 KB Output is correct
119 Correct 581 ms 98756 KB Output is correct
120 Correct 609 ms 98760 KB Output is correct
121 Correct 620 ms 98864 KB Output is correct
122 Correct 588 ms 98752 KB Output is correct
123 Correct 88 ms 92748 KB Output is correct
124 Correct 718 ms 97872 KB Output is correct
125 Correct 558 ms 95064 KB Output is correct
126 Correct 723 ms 98440 KB Output is correct
127 Correct 757 ms 98700 KB Output is correct
128 Correct 813 ms 98736 KB Output is correct
129 Correct 830 ms 98644 KB Output is correct
130 Correct 757 ms 98548 KB Output is correct
131 Correct 170 ms 101712 KB Output is correct
132 Correct 164 ms 103244 KB Output is correct
133 Correct 155 ms 98384 KB Output is correct
134 Correct 1240 ms 97752 KB Output is correct
135 Correct 1378 ms 97608 KB Output is correct
136 Correct 1044 ms 97620 KB Output is correct
137 Correct 177 ms 99136 KB Output is correct
138 Correct 208 ms 99172 KB Output is correct
139 Correct 179 ms 99184 KB Output is correct
140 Correct 188 ms 99016 KB Output is correct
141 Correct 200 ms 99184 KB Output is correct
142 Correct 204 ms 99104 KB Output is correct
143 Correct 228 ms 86464 KB Output is correct
144 Correct 818 ms 98128 KB Output is correct