oj.uz

Submission #873888

# Submission time Handle Problem Language Result Execution time Memory
873888 2023-11-16T02:31:32 Z MinaRagy06 Tourism (JOI23_tourism) C++17
24 / 100
 744 ms 91712 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

int lazy[18][1 << 18];
void inc(int lvl, int i, int l, int r, int s, int e) {
	if (s <= l && r <= e) {
		lazy[lvl][i]++;
		return;
	}
	if (r < s || e < l) {
		return;
	}
	inc(lvl, i << 1, l, md, s, e);
	inc(lvl, i << 1 | 1, md + 1, r, s, e);
}
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 = 100'005;
int anc[18][N], h[N], height;
vector<int> adj[N];
void dfs(int i, int d, int p) {
	h[i] = d;
	height = max(height, d);
	anc[0][i] = p;
	for (int j = 1; j < 18; j++) {
		anc[j][i] = anc[j - 1][anc[j - 1][i]];
	}
	for (auto nxt : adj[i]) {
		if (nxt == p) continue;
		dfs(nxt, d + 1, i);
	}
}
int lst[18][N], 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]);
}
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);
	int a[m];
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		sparse[0][i] = a[i];
	}
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i < 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});
	}
	memset(lst, -1, sizeof lst);
	int ans[q]{};
	for (int r = 0; r < m; r++) {
		for (int j = h[a[r]]; j >= 0; j--) {
			inc(j, 1, 0, m - 1, lst[j][a[r]] + 1, r);
			lst[j][a[r]] = r;
			a[r] = anc[0][a[r]];
		}
		for (auto [l, idx] : ask[r]) {
			int lca = query(l, r);
			int mn = h[lca];
			for (int j = height; j >= mn; j--) {
				int v = get(j, 1, 0, m - 1, l);
				ans[idx] += v;
			}
		}
	}
	for (auto i : ans) {
		cout << i << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 6 ms 38748 KB Output is correct
5 Correct 7 ms 34648 KB Output is correct
6 Correct 6 ms 36700 KB Output is correct
7 Correct 5 ms 34648 KB Output is correct
8 Incorrect 6 ms 34652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 6 ms 38748 KB Output is correct
5 Correct 7 ms 34648 KB Output is correct
6 Correct 6 ms 36700 KB Output is correct
7 Correct 5 ms 34648 KB Output is correct
8 Incorrect 6 ms 34652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28484 KB Output is correct
2 Correct 4 ms 10072 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Runtime error 209 ms 65008 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 4 ms 26204 KB Output is correct
2 Runtime error 108 ms 91712 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26204 KB Output is correct
2 Correct 5 ms 24396 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 557 ms 49716 KB Output is correct
5 Correct 563 ms 50876 KB Output is correct
6 Correct 687 ms 52548 KB Output is correct
7 Correct 721 ms 53284 KB Output is correct
8 Correct 744 ms 53372 KB Output is correct
9 Correct 611 ms 53292 KB Output is correct
10 Correct 656 ms 53356 KB Output is correct
11 Correct 708 ms 53368 KB Output is correct
12 Correct 658 ms 53292 KB Output is correct
13 Correct 613 ms 53352 KB Output is correct
14 Correct 100 ms 33912 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 6 ms 38748 KB Output is correct
5 Correct 7 ms 34648 KB Output is correct
6 Correct 6 ms 36700 KB Output is correct
7 Correct 5 ms 34648 KB Output is correct
8 Incorrect 6 ms 34652 KB Output isn't correct
9 Halted 0 ms 0 KB -