oj.uz

Submission #874675

# Submission time Handle Problem Language Result Execution time Memory
874675 2023-11-17T15:19:52 Z MinaRagy06 Tourism (JOI23_tourism) C++17
5 / 100
 46 ms 57284 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

int lazy[36][1 << 18];
void add(int lvl, int i, int l, int r, int s, int e, int v) {
	if (s <= l && r <= e) {
		lazy[lvl][i] += v;
		return;
	}
	if (r < s || e < l) {
		return;
	}
	add(lvl, i << 1, l, md, s, e, v);
	add(lvl, i << 1 | 1, md + 1, r, s, e, v);
}
int get(int lvl, int i, int l, int r, int x) {
	if (l == r) {
		return lazy[lvl][i];
	}
	if (x <= md) {
		return get(lvl, i << 1, l, md, x) + lazy[lvl][i];
	} else {
		return get(lvl, i << 1 | 1, md + 1, r, x) + lazy[lvl][i];
	}
}
const int N = 1'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[36][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 a[m];
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		sparse[0][i] = mp[a[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, 2>> ask[m];
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		ask[r].push_back({l, i});
	}
	for (int j = 0; j < 18; j++) {
		for (int i = 0; i <= n; i++) {
			s[j][i].push({(int)1e9, -1});
			s[18 + j][i].push({(int)-1e9, -1});
		}
	}
	int ans[q]{};
	for (int r = 0; r < m; r++) {
		int curh = mph[a[r]];
		a[r] = mp[a[r]];
// 		cout << '\n' << r << ": \n";
		for (int j = h[a[r]]; j >= 0; j--) {
			// j -> mx[l, i], 18 + j -> mn[l, i]
			// {val, pos}
			add(j, 1, 0, m - 1, s[j][a[r]].top()[1] + 1, r, curh + 1);
// 			cout << s[j][a[r]].top()[1] + 1 << ' ' << r << ' ' << curh + 1 << '\n';
			while (curh >= s[j][a[r]].top()[0]) {
				array<int, 2> lst = s[j][a[r]].top();
				s[j][a[r]].pop();
				add(j, 1, 0, m - 1, s[j][a[r]].top()[1] + 1, lst[1], curh - lst[0]);
			}
			s[j][a[r]].push({curh, r});
			add(18 + j, 1, 0, m - 1, s[18 + j][a[r]].top()[1] + 1, r, curh);
			while (curh <= s[18 + j][a[r]].top()[0]) {
				array<int, 2> lst = s[18 + j][a[r]].top();
				s[18 + j][a[r]].pop();
				add(18 + j, 1, 0, m - 1, s[18 + j][a[r]].top()[1] + 1, lst[1], curh - lst[0]);
			}
			s[18 + j][a[r]].push({curh, r});

			a[r] = anc[0][a[r]];
			curh = mxh[a[r]];
		}
		for (auto [l, idx] : ask[r]) {
			int lca = query(l, r);
			int mnh = h[lca];
// 			cout << lca << '\n';
// 			cout << mnh << "|\n";
			for (int j = height; j >= mnh; j--) {
				int v = get(j, 1, 0, m - 1, l);
				ans[idx] += v;
// 				cout << v << '\n';
				if (j == mnh) {
					int v2 = get(18 + j, 1, 0, m - 1, l);
// 					cout << '.' << v2 << '\n';
					ans[idx] -= v2;
				}
			}
		}
	}
	for (auto i : ans) {
		cout << i << '\n';
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32348 KB Output is correct
2 Correct 12 ms 28260 KB Output is correct
3 Correct 15 ms 32348 KB Output is correct
4 Correct 16 ms 48836 KB Output is correct
5 Correct 15 ms 46684 KB Output is correct
6 Correct 15 ms 48796 KB Output is correct
7 Correct 14 ms 44632 KB Output is correct
8 Correct 15 ms 48728 KB Output is correct
9 Correct 17 ms 46940 KB Output is correct
10 Correct 16 ms 54872 KB Output is correct
11 Correct 17 ms 54876 KB Output is correct
12 Correct 16 ms 56924 KB Output is correct
13 Correct 15 ms 52828 KB Output is correct
14 Correct 15 ms 48732 KB Output is correct
15 Correct 12 ms 28252 KB Output is correct
16 Correct 14 ms 28252 KB Output is correct
17 Correct 12 ms 28364 KB Output is correct
18 Correct 14 ms 40540 KB Output is correct
19 Correct 13 ms 36340 KB Output is correct
20 Correct 13 ms 34396 KB Output is correct
21 Correct 13 ms 28356 KB Output is correct
22 Correct 12 ms 28360 KB Output is correct
23 Correct 12 ms 28248 KB Output is correct
24 Correct 12 ms 28252 KB Output is correct
25 Correct 11 ms 28252 KB Output is correct
26 Correct 12 ms 28252 KB Output is correct
27 Correct 12 ms 28308 KB Output is correct
28 Correct 15 ms 40540 KB Output is correct
29 Correct 16 ms 42908 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32348 KB Output is correct
2 Correct 12 ms 28260 KB Output is correct
3 Correct 15 ms 32348 KB Output is correct
4 Correct 16 ms 48836 KB Output is correct
5 Correct 15 ms 46684 KB Output is correct
6 Correct 15 ms 48796 KB Output is correct
7 Correct 14 ms 44632 KB Output is correct
8 Correct 15 ms 48728 KB Output is correct
9 Correct 17 ms 46940 KB Output is correct
10 Correct 16 ms 54872 KB Output is correct
11 Correct 17 ms 54876 KB Output is correct
12 Correct 16 ms 56924 KB Output is correct
13 Correct 15 ms 52828 KB Output is correct
14 Correct 15 ms 48732 KB Output is correct
15 Correct 12 ms 28252 KB Output is correct
16 Correct 14 ms 28252 KB Output is correct
17 Correct 12 ms 28364 KB Output is correct
18 Correct 14 ms 40540 KB Output is correct
19 Correct 13 ms 36340 KB Output is correct
20 Correct 13 ms 34396 KB Output is correct
21 Correct 13 ms 28356 KB Output is correct
22 Correct 12 ms 28360 KB Output is correct
23 Correct 12 ms 28248 KB Output is correct
24 Correct 12 ms 28252 KB Output is correct
25 Correct 11 ms 28252 KB Output is correct
26 Correct 12 ms 28252 KB Output is correct
27 Correct 12 ms 28308 KB Output is correct
28 Correct 15 ms 40540 KB Output is correct
29 Correct 16 ms 42908 KB Output is correct
30 Runtime error 33 ms 52828 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28252 KB Output is correct
2 Correct 13 ms 28252 KB Output is correct
3 Correct 14 ms 28252 KB Output is correct
4 Runtime error 45 ms 57284 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32348 KB Output is correct
2 Runtime error 43 ms 57152 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32344 KB Output is correct
2 Correct 12 ms 28252 KB Output is correct
3 Correct 13 ms 28248 KB Output is correct
4 Runtime error 46 ms 57172 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32348 KB Output is correct
2 Correct 12 ms 28260 KB Output is correct
3 Correct 15 ms 32348 KB Output is correct
4 Correct 16 ms 48836 KB Output is correct
5 Correct 15 ms 46684 KB Output is correct
6 Correct 15 ms 48796 KB Output is correct
7 Correct 14 ms 44632 KB Output is correct
8 Correct 15 ms 48728 KB Output is correct
9 Correct 17 ms 46940 KB Output is correct
10 Correct 16 ms 54872 KB Output is correct
11 Correct 17 ms 54876 KB Output is correct
12 Correct 16 ms 56924 KB Output is correct
13 Correct 15 ms 52828 KB Output is correct
14 Correct 15 ms 48732 KB Output is correct
15 Correct 12 ms 28252 KB Output is correct
16 Correct 14 ms 28252 KB Output is correct
17 Correct 12 ms 28364 KB Output is correct
18 Correct 14 ms 40540 KB Output is correct
19 Correct 13 ms 36340 KB Output is correct
20 Correct 13 ms 34396 KB Output is correct
21 Correct 13 ms 28356 KB Output is correct
22 Correct 12 ms 28360 KB Output is correct
23 Correct 12 ms 28248 KB Output is correct
24 Correct 12 ms 28252 KB Output is correct
25 Correct 11 ms 28252 KB Output is correct
26 Correct 12 ms 28252 KB Output is correct
27 Correct 12 ms 28308 KB Output is correct
28 Correct 15 ms 40540 KB Output is correct
29 Correct 16 ms 42908 KB Output is correct
30 Runtime error 33 ms 52828 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -