oj.uz

Submission #874686

# Submission time Handle Problem Language Result Execution time Memory
874686 2023-11-17T16:05:49 Z MinaRagy06 Tourism (JOI23_tourism) C++17
100 / 100
 3389 ms 104892 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

int lazy[1 << 18];
void add(int i, int l, int r, int s, int e, int v) {
	if (s <= l && r <= e) {
		lazy[i] += v;
		return;
	}
	if (r < s || e < l) {
		return;
	}
	add(i << 1, l, md, s, e, v);
	add(i << 1 | 1, md + 1, r, s, e, v);
}
int get(int i, int l, int r, int x) {
	if (l == r) {
		return lazy[i];
	}
	if (x <= md) {
		return get(i << 1, l, md, x) + lazy[i];
	} else {
		return get(i << 1 | 1, md + 1, r, x) + lazy[i];
	}
}
const int N = 100'005;
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);
	int n, m, q;
	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(lazy, 0, sizeof lazy);
		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(1, 0, m - 1, 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(1, 0, m - 1, 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(1, 0, m - 1, 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(lazy, 0, sizeof lazy);
		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(1, 0, m - 1, s[cura].top()[1] + 1, r, curh);
			while (curh <= s[cura].top()[0]) {
				array<int, 2> lst = s[cura].top();
				s[cura].pop();
				add(1, 0, m - 1, 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(1, 0, m - 1, 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 37 ms 82524 KB Output is correct
2 Correct 36 ms 82520 KB Output is correct
3 Correct 36 ms 82688 KB Output is correct
4 Correct 37 ms 84640 KB Output is correct
5 Correct 37 ms 84664 KB Output is correct
6 Correct 39 ms 84932 KB Output is correct
7 Correct 38 ms 84572 KB Output is correct
8 Correct 45 ms 84804 KB Output is correct
9 Correct 39 ms 84576 KB Output is correct
10 Correct 41 ms 84560 KB Output is correct
11 Correct 38 ms 84572 KB Output is correct
12 Correct 38 ms 84700 KB Output is correct
13 Correct 37 ms 84572 KB Output is correct
14 Correct 42 ms 84620 KB Output is correct
15 Correct 38 ms 84592 KB Output is correct
16 Correct 38 ms 84572 KB Output is correct
17 Correct 36 ms 84560 KB Output is correct
18 Correct 38 ms 84564 KB Output is correct
19 Correct 37 ms 84572 KB Output is correct
20 Correct 39 ms 84568 KB Output is correct
21 Correct 37 ms 84572 KB Output is correct
22 Correct 42 ms 85012 KB Output is correct
23 Correct 37 ms 84564 KB Output is correct
24 Correct 37 ms 84560 KB Output is correct
25 Correct 37 ms 84780 KB Output is correct
26 Correct 39 ms 84568 KB Output is correct
27 Correct 41 ms 84572 KB Output is correct
28 Correct 37 ms 80476 KB Output is correct
29 Correct 43 ms 84812 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 82524 KB Output is correct
2 Correct 36 ms 82520 KB Output is correct
3 Correct 36 ms 82688 KB Output is correct
4 Correct 37 ms 84640 KB Output is correct
5 Correct 37 ms 84664 KB Output is correct
6 Correct 39 ms 84932 KB Output is correct
7 Correct 38 ms 84572 KB Output is correct
8 Correct 45 ms 84804 KB Output is correct
9 Correct 39 ms 84576 KB Output is correct
10 Correct 41 ms 84560 KB Output is correct
11 Correct 38 ms 84572 KB Output is correct
12 Correct 38 ms 84700 KB Output is correct
13 Correct 37 ms 84572 KB Output is correct
14 Correct 42 ms 84620 KB Output is correct
15 Correct 38 ms 84592 KB Output is correct
16 Correct 38 ms 84572 KB Output is correct
17 Correct 36 ms 84560 KB Output is correct
18 Correct 38 ms 84564 KB Output is correct
19 Correct 37 ms 84572 KB Output is correct
20 Correct 39 ms 84568 KB Output is correct
21 Correct 37 ms 84572 KB Output is correct
22 Correct 42 ms 85012 KB Output is correct
23 Correct 37 ms 84564 KB Output is correct
24 Correct 37 ms 84560 KB Output is correct
25 Correct 37 ms 84780 KB Output is correct
26 Correct 39 ms 84568 KB Output is correct
27 Correct 41 ms 84572 KB Output is correct
28 Correct 37 ms 80476 KB Output is correct
29 Correct 43 ms 84812 KB Output is correct
30 Correct 45 ms 84904 KB Output is correct
31 Correct 50 ms 84820 KB Output is correct
32 Correct 49 ms 84748 KB Output is correct
33 Correct 57 ms 84824 KB Output is correct
34 Correct 51 ms 84828 KB Output is correct
35 Correct 50 ms 84824 KB Output is correct
36 Correct 51 ms 84816 KB Output is correct
37 Correct 52 ms 84936 KB Output is correct
38 Correct 39 ms 85028 KB Output is correct
39 Correct 42 ms 84936 KB Output is correct
40 Correct 44 ms 84820 KB Output is correct
41 Correct 43 ms 84828 KB Output is correct
42 Correct 40 ms 84884 KB Output is correct
43 Correct 39 ms 84820 KB Output is correct
44 Correct 46 ms 84972 KB Output is correct
45 Correct 46 ms 84816 KB Output is correct
46 Correct 59 ms 85080 KB Output is correct
47 Correct 45 ms 84916 KB Output is correct
48 Correct 46 ms 84816 KB Output is correct
49 Correct 47 ms 84836 KB Output is correct
50 Correct 44 ms 84824 KB Output is correct
51 Correct 44 ms 84984 KB Output is correct
52 Correct 40 ms 84848 KB Output is correct
53 Correct 39 ms 84816 KB Output is correct
54 Correct 39 ms 84820 KB Output is correct
55 Correct 40 ms 84816 KB Output is correct
56 Correct 43 ms 84888 KB Output is correct
57 Correct 39 ms 80728 KB Output is correct
58 Correct 50 ms 84820 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 82516 KB Output is correct
2 Correct 37 ms 84568 KB Output is correct
3 Correct 39 ms 84824 KB Output is correct
4 Correct 143 ms 97688 KB Output is correct
5 Correct 120 ms 100476 KB Output is correct
6 Correct 137 ms 101984 KB Output is correct
7 Correct 168 ms 104884 KB Output is correct
8 Correct 172 ms 104788 KB Output is correct
9 Correct 178 ms 104884 KB Output is correct
10 Correct 169 ms 104892 KB Output is correct
11 Correct 180 ms 104780 KB Output is correct
12 Correct 153 ms 104400 KB Output is correct
13 Correct 158 ms 104444 KB Output is correct
14 Correct 154 ms 104536 KB Output is correct
15 Correct 77 ms 96144 KB Output is correct
16 Correct 170 ms 104452 KB Output is correct
17 Correct 151 ms 94224 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82524 KB Output is correct
2 Correct 569 ms 91496 KB Output is correct
3 Correct 955 ms 93144 KB Output is correct
4 Correct 800 ms 92780 KB Output is correct
5 Correct 1058 ms 95292 KB Output is correct
6 Correct 1343 ms 95288 KB Output is correct
7 Correct 1108 ms 95488 KB Output is correct
8 Correct 1144 ms 95336 KB Output is correct
9 Correct 1126 ms 95288 KB Output is correct
10 Correct 1291 ms 95384 KB Output is correct
11 Correct 1190 ms 95340 KB Output is correct
12 Correct 1474 ms 95424 KB Output is correct
13 Correct 1163 ms 95748 KB Output is correct
14 Correct 1214 ms 96708 KB Output is correct
15 Correct 1537 ms 100120 KB Output is correct
16 Correct 1372 ms 95760 KB Output is correct
17 Correct 1253 ms 95568 KB Output is correct
18 Correct 1294 ms 95760 KB Output is correct
19 Correct 2453 ms 95132 KB Output is correct
20 Correct 1906 ms 95180 KB Output is correct
21 Correct 1797 ms 95180 KB Output is correct
22 Correct 2279 ms 95180 KB Output is correct
23 Correct 2174 ms 95172 KB Output is correct
24 Correct 2175 ms 95312 KB Output is correct
25 Correct 2189 ms 95180 KB Output is correct
26 Correct 2263 ms 95264 KB Output is correct
27 Correct 2163 ms 95204 KB Output is correct
28 Correct 1961 ms 95232 KB Output is correct
29 Correct 2120 ms 95268 KB Output is correct
30 Correct 2190 ms 95408 KB Output is correct
31 Correct 2070 ms 95656 KB Output is correct
32 Correct 2015 ms 96112 KB Output is correct
33 Correct 1889 ms 97512 KB Output is correct
34 Correct 2878 ms 99888 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 82512 KB Output is correct
2 Correct 36 ms 84572 KB Output is correct
3 Correct 41 ms 84636 KB Output is correct
4 Correct 1149 ms 96872 KB Output is correct
5 Correct 1143 ms 97108 KB Output is correct
6 Correct 1327 ms 98384 KB Output is correct
7 Correct 1357 ms 99396 KB Output is correct
8 Correct 1345 ms 99392 KB Output is correct
9 Correct 1347 ms 99412 KB Output is correct
10 Correct 1393 ms 99244 KB Output is correct
11 Correct 1350 ms 99392 KB Output is correct
12 Correct 1345 ms 99588 KB Output is correct
13 Correct 1408 ms 99388 KB Output is correct
14 Correct 130 ms 94288 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 82524 KB Output is correct
2 Correct 36 ms 82520 KB Output is correct
3 Correct 36 ms 82688 KB Output is correct
4 Correct 37 ms 84640 KB Output is correct
5 Correct 37 ms 84664 KB Output is correct
6 Correct 39 ms 84932 KB Output is correct
7 Correct 38 ms 84572 KB Output is correct
8 Correct 45 ms 84804 KB Output is correct
9 Correct 39 ms 84576 KB Output is correct
10 Correct 41 ms 84560 KB Output is correct
11 Correct 38 ms 84572 KB Output is correct
12 Correct 38 ms 84700 KB Output is correct
13 Correct 37 ms 84572 KB Output is correct
14 Correct 42 ms 84620 KB Output is correct
15 Correct 38 ms 84592 KB Output is correct
16 Correct 38 ms 84572 KB Output is correct
17 Correct 36 ms 84560 KB Output is correct
18 Correct 38 ms 84564 KB Output is correct
19 Correct 37 ms 84572 KB Output is correct
20 Correct 39 ms 84568 KB Output is correct
21 Correct 37 ms 84572 KB Output is correct
22 Correct 42 ms 85012 KB Output is correct
23 Correct 37 ms 84564 KB Output is correct
24 Correct 37 ms 84560 KB Output is correct
25 Correct 37 ms 84780 KB Output is correct
26 Correct 39 ms 84568 KB Output is correct
27 Correct 41 ms 84572 KB Output is correct
28 Correct 37 ms 80476 KB Output is correct
29 Correct 43 ms 84812 KB Output is correct
30 Correct 45 ms 84904 KB Output is correct
31 Correct 50 ms 84820 KB Output is correct
32 Correct 49 ms 84748 KB Output is correct
33 Correct 57 ms 84824 KB Output is correct
34 Correct 51 ms 84828 KB Output is correct
35 Correct 50 ms 84824 KB Output is correct
36 Correct 51 ms 84816 KB Output is correct
37 Correct 52 ms 84936 KB Output is correct
38 Correct 39 ms 85028 KB Output is correct
39 Correct 42 ms 84936 KB Output is correct
40 Correct 44 ms 84820 KB Output is correct
41 Correct 43 ms 84828 KB Output is correct
42 Correct 40 ms 84884 KB Output is correct
43 Correct 39 ms 84820 KB Output is correct
44 Correct 46 ms 84972 KB Output is correct
45 Correct 46 ms 84816 KB Output is correct
46 Correct 59 ms 85080 KB Output is correct
47 Correct 45 ms 84916 KB Output is correct
48 Correct 46 ms 84816 KB Output is correct
49 Correct 47 ms 84836 KB Output is correct
50 Correct 44 ms 84824 KB Output is correct
51 Correct 44 ms 84984 KB Output is correct
52 Correct 40 ms 84848 KB Output is correct
53 Correct 39 ms 84816 KB Output is correct
54 Correct 39 ms 84820 KB Output is correct
55 Correct 40 ms 84816 KB Output is correct
56 Correct 43 ms 84888 KB Output is correct
57 Correct 39 ms 80728 KB Output is correct
58 Correct 50 ms 84820 KB Output is correct
59 Correct 37 ms 82516 KB Output is correct
60 Correct 37 ms 84568 KB Output is correct
61 Correct 39 ms 84824 KB Output is correct
62 Correct 143 ms 97688 KB Output is correct
63 Correct 120 ms 100476 KB Output is correct
64 Correct 137 ms 101984 KB Output is correct
65 Correct 168 ms 104884 KB Output is correct
66 Correct 172 ms 104788 KB Output is correct
67 Correct 178 ms 104884 KB Output is correct
68 Correct 169 ms 104892 KB Output is correct
69 Correct 180 ms 104780 KB Output is correct
70 Correct 153 ms 104400 KB Output is correct
71 Correct 158 ms 104444 KB Output is correct
72 Correct 154 ms 104536 KB Output is correct
73 Correct 77 ms 96144 KB Output is correct
74 Correct 170 ms 104452 KB Output is correct
75 Correct 151 ms 94224 KB Output is correct
76 Correct 36 ms 82524 KB Output is correct
77 Correct 569 ms 91496 KB Output is correct
78 Correct 955 ms 93144 KB Output is correct
79 Correct 800 ms 92780 KB Output is correct
80 Correct 1058 ms 95292 KB Output is correct
81 Correct 1343 ms 95288 KB Output is correct
82 Correct 1108 ms 95488 KB Output is correct
83 Correct 1144 ms 95336 KB Output is correct
84 Correct 1126 ms 95288 KB Output is correct
85 Correct 1291 ms 95384 KB Output is correct
86 Correct 1190 ms 95340 KB Output is correct
87 Correct 1474 ms 95424 KB Output is correct
88 Correct 1163 ms 95748 KB Output is correct
89 Correct 1214 ms 96708 KB Output is correct
90 Correct 1537 ms 100120 KB Output is correct
91 Correct 1372 ms 95760 KB Output is correct
92 Correct 1253 ms 95568 KB Output is correct
93 Correct 1294 ms 95760 KB Output is correct
94 Correct 2453 ms 95132 KB Output is correct
95 Correct 1906 ms 95180 KB Output is correct
96 Correct 1797 ms 95180 KB Output is correct
97 Correct 2279 ms 95180 KB Output is correct
98 Correct 2174 ms 95172 KB Output is correct
99 Correct 2175 ms 95312 KB Output is correct
100 Correct 2189 ms 95180 KB Output is correct
101 Correct 2263 ms 95264 KB Output is correct
102 Correct 2163 ms 95204 KB Output is correct
103 Correct 1961 ms 95232 KB Output is correct
104 Correct 2120 ms 95268 KB Output is correct
105 Correct 2190 ms 95408 KB Output is correct
106 Correct 2070 ms 95656 KB Output is correct
107 Correct 2015 ms 96112 KB Output is correct
108 Correct 1889 ms 97512 KB Output is correct
109 Correct 2878 ms 99888 KB Output is correct
110 Correct 39 ms 82512 KB Output is correct
111 Correct 36 ms 84572 KB Output is correct
112 Correct 41 ms 84636 KB Output is correct
113 Correct 1149 ms 96872 KB Output is correct
114 Correct 1143 ms 97108 KB Output is correct
115 Correct 1327 ms 98384 KB Output is correct
116 Correct 1357 ms 99396 KB Output is correct
117 Correct 1345 ms 99392 KB Output is correct
118 Correct 1347 ms 99412 KB Output is correct
119 Correct 1393 ms 99244 KB Output is correct
120 Correct 1350 ms 99392 KB Output is correct
121 Correct 1345 ms 99588 KB Output is correct
122 Correct 1408 ms 99388 KB Output is correct
123 Correct 130 ms 94288 KB Output is correct
124 Correct 1461 ms 98716 KB Output is correct
125 Correct 1187 ms 96036 KB Output is correct
126 Correct 1585 ms 99668 KB Output is correct
127 Correct 1631 ms 99512 KB Output is correct
128 Correct 1835 ms 99508 KB Output is correct
129 Correct 1879 ms 99768 KB Output is correct
130 Correct 1712 ms 99520 KB Output is correct
131 Correct 249 ms 103480 KB Output is correct
132 Correct 250 ms 104632 KB Output is correct
133 Correct 238 ms 100180 KB Output is correct
134 Correct 3205 ms 99408 KB Output is correct
135 Correct 3389 ms 99412 KB Output is correct
136 Correct 2499 ms 99428 KB Output is correct
137 Correct 260 ms 99788 KB Output is correct
138 Correct 282 ms 99820 KB Output is correct
139 Correct 263 ms 99840 KB Output is correct
140 Correct 285 ms 99752 KB Output is correct
141 Correct 291 ms 100000 KB Output is correct
142 Correct 288 ms 99644 KB Output is correct
143 Correct 219 ms 87140 KB Output is correct
144 Correct 1687 ms 99076 KB Output is correct