oj.uz

Submission #743887

# Submission time Handle Problem Language Result Execution time Memory
743887 2023-05-18T05:50:31 Z pavement Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 34196 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple

using ii = pair<int, int>;
using iiii = tuple<int, int, int, int>;

const int BLK_SZ = 300;
int N, M, Q, wL, wR = -1, idx, cur, sv_cur, out[100005], C[100005], L[100005], R[100005], pre[100005], dep[100005], ll[100005], rr[100005], anc[25][100005];
iiii T[100005];
vector<int> adj[100005];
multiset<ii> S;
map<ii, int> seen;

void dfs(int n, int e = -1) {
	pre[n] = ++idx;
	for (int k = 1; k <= 17; k++) {
		if (anc[k - 1][n] == -1) break;
		anc[k][n] = anc[k - 1][anc[k - 1][n]];
	}
	for (auto u : adj[n]) if (u != e) {
		anc[0][u] = n;
		dep[u] = dep[n] + 1;
		dfs(u, n);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int k = 17; k >= 0; k--) {
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	}
	if (u == v) return u;
	for (int k = 17; k >= 0; k--) {
		if (anc[k][u] != anc[k][v]) {
			u = anc[k][u];
			v = anc[k][v];
		}
	}
	return anc[0][u];
}

int dist(int u, int v) {
	if (seen.find(mp(u, v)) != seen.end()) return seen[mp(u, v)];
	if (seen.find(mp(v, u)) != seen.end()) return seen[mp(v, u)];
	int w = lca(u, v);
	return seen[mp(u, v)] = dep[u] + dep[v] - 2 * dep[w];
}

void add_path(int u, int v) {
	cur += dist(u, v);
}

void rem_path(int u, int v) {
	cur -= dist(u, v);	
}

void add(int k) {
	S.emplace(pre[k], k);
	auto it = S.find(mp(pre[k], k));
	ii x = mp(-1, -1), y = mp(-1, -1);
	if (it != S.begin()) {
		--it;
		x = *it;
		++it;
	}
	++it;
	if (it != S.end()) {
		y = *it;
	}
	--it;
	if (x.first != -1 && y.first != -1) {
		rem_path(x.second, y.second);
	} else if (x.first == -1 && y.first != -1) {
		auto it2 = --S.end();
		rem_path(y.second, it2->second);
	} else if (y.first == -1 && x.first != -1) {
		auto it2 = S.begin();
		rem_path(x.second, it2->second);
	}
	if (x.first == -1 && y.first == -1) {}
	else if (x.first == -1) {
		auto it2 = --S.end();
		add_path(it2->second, k);
		add_path(k, y.second);
	} else if (y.first == -1) {
		auto it2 = S.begin();
		add_path(x.second, k);
		add_path(k, it2->second);
	} else {
		add_path(x.second, k);
		add_path(k, y.second);
	}
}

void rem(int k) {
	S.erase(S.find(mp(pre[k], k)));
}

int main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i++) {
		if (ll[i / BLK_SZ] == 0) ll[i / BLK_SZ] = i;
		rr[i / BLK_SZ] = i;
	}
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	for (int i = 1; i <= M; i++) {
		cin >> C[i];
	}
	for (int i = 1; i <= Q; i++) {
		cin >> L[i] >> R[i];
		T[i] = mt(L[i] / BLK_SZ, R[i], L[i], i);
	}
	sort(T + 1, T + 1 + Q);
	for (int i = 1; i <= Q; i++) {
		auto [_, r, l, idx] = T[i];
		L[i] = l;
		R[i] = r;
		if (L[i] / BLK_SZ == R[i] / BLK_SZ) {
			continue;
		}
		// move window to [L[i], R[i]]
		if (wR == -1 || wL / BLK_SZ - 1 != L[i] / BLK_SZ) {
			for (int j = wL; j <= wR; j++) rem(C[j]);
			cur = 0;
			for (int j = rr[L[i] / BLK_SZ] + 1; j <= R[i]; j++) add(C[j]);
			sv_cur = cur;
			for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) add(C[j]);
			out[idx] = cur / 2 + 1;
			for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
			cur = sv_cur;
			wL = rr[L[i] / BLK_SZ] + 1;
			wR = R[i];
			continue;
		}
		for (int j = wR + 1; j <= R[i]; j++) add(C[j]);
		sv_cur = cur;
		for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) add(C[j]);
		out[idx] = cur / 2 + 1;
		for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
		cur = sv_cur;
		wL = rr[L[i] / BLK_SZ] + 1;
		wR = R[i];
	}
	for (int i = wL; i <= wR; i++) rem(C[i]);
	cur = 0;
	for (int i = 1; i <= Q; i++) {
		if (L[i] / BLK_SZ == R[i] / BLK_SZ) {
			for (int j = L[i]; j <= R[i]; j++) add(C[j]);
			out[get<3>(T[i])] = cur / 2 + 1;
			for (int j = L[i]; j <= R[i]; j++) rem(C[j]);
			cur = 0;
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << out[i] << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12372 KB Output is correct
3 Correct 6 ms 12372 KB Output is correct
4 Correct 24 ms 12500 KB Output is correct
5 Correct 16 ms 12500 KB Output is correct
6 Correct 17 ms 12500 KB Output is correct
7 Correct 20 ms 12592 KB Output is correct
8 Correct 14 ms 12500 KB Output is correct
9 Correct 34 ms 12756 KB Output is correct
10 Correct 28 ms 12664 KB Output is correct
11 Correct 27 ms 12644 KB Output is correct
12 Correct 59 ms 12580 KB Output is correct
13 Correct 67 ms 12696 KB Output is correct
14 Correct 62 ms 12500 KB Output is correct
15 Correct 29 ms 12628 KB Output is correct
16 Correct 26 ms 12632 KB Output is correct
17 Correct 29 ms 12656 KB Output is correct
18 Correct 28 ms 12624 KB Output is correct
19 Correct 35 ms 12628 KB Output is correct
20 Correct 37 ms 12656 KB Output is correct
21 Correct 38 ms 12632 KB Output is correct
22 Correct 31 ms 12544 KB Output is correct
23 Correct 28 ms 12632 KB Output is correct
24 Correct 29 ms 12628 KB Output is correct
25 Correct 30 ms 12664 KB Output is correct
26 Correct 29 ms 12624 KB Output is correct
27 Correct 11 ms 12516 KB Output is correct
28 Correct 6 ms 12408 KB Output is correct
29 Correct 7 ms 12500 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12372 KB Output is correct
3 Correct 6 ms 12372 KB Output is correct
4 Correct 24 ms 12500 KB Output is correct
5 Correct 16 ms 12500 KB Output is correct
6 Correct 17 ms 12500 KB Output is correct
7 Correct 20 ms 12592 KB Output is correct
8 Correct 14 ms 12500 KB Output is correct
9 Correct 34 ms 12756 KB Output is correct
10 Correct 28 ms 12664 KB Output is correct
11 Correct 27 ms 12644 KB Output is correct
12 Correct 59 ms 12580 KB Output is correct
13 Correct 67 ms 12696 KB Output is correct
14 Correct 62 ms 12500 KB Output is correct
15 Correct 29 ms 12628 KB Output is correct
16 Correct 26 ms 12632 KB Output is correct
17 Correct 29 ms 12656 KB Output is correct
18 Correct 28 ms 12624 KB Output is correct
19 Correct 35 ms 12628 KB Output is correct
20 Correct 37 ms 12656 KB Output is correct
21 Correct 38 ms 12632 KB Output is correct
22 Correct 31 ms 12544 KB Output is correct
23 Correct 28 ms 12632 KB Output is correct
24 Correct 29 ms 12628 KB Output is correct
25 Correct 30 ms 12664 KB Output is correct
26 Correct 29 ms 12624 KB Output is correct
27 Correct 11 ms 12516 KB Output is correct
28 Correct 6 ms 12408 KB Output is correct
29 Correct 7 ms 12500 KB Output is correct
30 Correct 188 ms 13440 KB Output is correct
31 Correct 222 ms 13388 KB Output is correct
32 Correct 280 ms 13640 KB Output is correct
33 Correct 263 ms 13636 KB Output is correct
34 Correct 258 ms 13700 KB Output is correct
35 Correct 491 ms 12912 KB Output is correct
36 Correct 491 ms 13036 KB Output is correct
37 Correct 470 ms 13036 KB Output is correct
38 Correct 259 ms 13724 KB Output is correct
39 Correct 280 ms 13760 KB Output is correct
40 Correct 257 ms 13772 KB Output is correct
41 Correct 519 ms 13016 KB Output is correct
42 Correct 478 ms 13020 KB Output is correct
43 Correct 463 ms 12980 KB Output is correct
44 Correct 282 ms 13752 KB Output is correct
45 Correct 258 ms 13816 KB Output is correct
46 Correct 299 ms 13812 KB Output is correct
47 Correct 478 ms 12952 KB Output is correct
48 Correct 456 ms 12940 KB Output is correct
49 Correct 513 ms 13008 KB Output is correct
50 Correct 283 ms 13620 KB Output is correct
51 Correct 251 ms 13564 KB Output is correct
52 Correct 277 ms 13772 KB Output is correct
53 Correct 268 ms 13660 KB Output is correct
54 Correct 294 ms 13648 KB Output is correct
55 Correct 265 ms 13672 KB Output is correct
56 Correct 52 ms 12632 KB Output is correct
57 Correct 8 ms 12628 KB Output is correct
58 Correct 8 ms 12640 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 11 ms 12500 KB Output is correct
3 Correct 64 ms 12628 KB Output is correct
4 Execution timed out 5022 ms 34196 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 161 ms 21436 KB Output is correct
3 Correct 317 ms 26188 KB Output is correct
4 Correct 235 ms 23600 KB Output is correct
5 Correct 525 ms 31168 KB Output is correct
6 Correct 460 ms 29464 KB Output is correct
7 Correct 434 ms 29288 KB Output is correct
8 Correct 522 ms 29268 KB Output is correct
9 Correct 453 ms 29384 KB Output is correct
10 Correct 469 ms 29284 KB Output is correct
11 Correct 437 ms 29288 KB Output is correct
12 Correct 367 ms 29056 KB Output is correct
13 Correct 344 ms 28428 KB Output is correct
14 Correct 254 ms 26344 KB Output is correct
15 Correct 98 ms 19688 KB Output is correct
16 Correct 369 ms 29808 KB Output is correct
17 Correct 364 ms 29692 KB Output is correct
18 Correct 415 ms 29740 KB Output is correct
19 Correct 390 ms 31104 KB Output is correct
20 Correct 451 ms 29888 KB Output is correct
21 Correct 452 ms 29320 KB Output is correct
22 Correct 492 ms 29456 KB Output is correct
23 Correct 438 ms 29392 KB Output is correct
24 Correct 474 ms 29376 KB Output is correct
25 Correct 457 ms 29264 KB Output is correct
26 Correct 459 ms 29320 KB Output is correct
27 Correct 436 ms 29264 KB Output is correct
28 Correct 464 ms 29256 KB Output is correct
29 Correct 462 ms 29196 KB Output is correct
30 Correct 456 ms 28972 KB Output is correct
31 Correct 374 ms 28444 KB Output is correct
32 Correct 408 ms 27352 KB Output is correct
33 Correct 232 ms 24376 KB Output is correct
34 Correct 108 ms 19740 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 13 ms 12520 KB Output is correct
3 Correct 64 ms 12636 KB Output is correct
4 Execution timed out 5099 ms 31300 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12372 KB Output is correct
3 Correct 6 ms 12372 KB Output is correct
4 Correct 24 ms 12500 KB Output is correct
5 Correct 16 ms 12500 KB Output is correct
6 Correct 17 ms 12500 KB Output is correct
7 Correct 20 ms 12592 KB Output is correct
8 Correct 14 ms 12500 KB Output is correct
9 Correct 34 ms 12756 KB Output is correct
10 Correct 28 ms 12664 KB Output is correct
11 Correct 27 ms 12644 KB Output is correct
12 Correct 59 ms 12580 KB Output is correct
13 Correct 67 ms 12696 KB Output is correct
14 Correct 62 ms 12500 KB Output is correct
15 Correct 29 ms 12628 KB Output is correct
16 Correct 26 ms 12632 KB Output is correct
17 Correct 29 ms 12656 KB Output is correct
18 Correct 28 ms 12624 KB Output is correct
19 Correct 35 ms 12628 KB Output is correct
20 Correct 37 ms 12656 KB Output is correct
21 Correct 38 ms 12632 KB Output is correct
22 Correct 31 ms 12544 KB Output is correct
23 Correct 28 ms 12632 KB Output is correct
24 Correct 29 ms 12628 KB Output is correct
25 Correct 30 ms 12664 KB Output is correct
26 Correct 29 ms 12624 KB Output is correct
27 Correct 11 ms 12516 KB Output is correct
28 Correct 6 ms 12408 KB Output is correct
29 Correct 7 ms 12500 KB Output is correct
30 Correct 188 ms 13440 KB Output is correct
31 Correct 222 ms 13388 KB Output is correct
32 Correct 280 ms 13640 KB Output is correct
33 Correct 263 ms 13636 KB Output is correct
34 Correct 258 ms 13700 KB Output is correct
35 Correct 491 ms 12912 KB Output is correct
36 Correct 491 ms 13036 KB Output is correct
37 Correct 470 ms 13036 KB Output is correct
38 Correct 259 ms 13724 KB Output is correct
39 Correct 280 ms 13760 KB Output is correct
40 Correct 257 ms 13772 KB Output is correct
41 Correct 519 ms 13016 KB Output is correct
42 Correct 478 ms 13020 KB Output is correct
43 Correct 463 ms 12980 KB Output is correct
44 Correct 282 ms 13752 KB Output is correct
45 Correct 258 ms 13816 KB Output is correct
46 Correct 299 ms 13812 KB Output is correct
47 Correct 478 ms 12952 KB Output is correct
48 Correct 456 ms 12940 KB Output is correct
49 Correct 513 ms 13008 KB Output is correct
50 Correct 283 ms 13620 KB Output is correct
51 Correct 251 ms 13564 KB Output is correct
52 Correct 277 ms 13772 KB Output is correct
53 Correct 268 ms 13660 KB Output is correct
54 Correct 294 ms 13648 KB Output is correct
55 Correct 265 ms 13672 KB Output is correct
56 Correct 52 ms 12632 KB Output is correct
57 Correct 8 ms 12628 KB Output is correct
58 Correct 8 ms 12640 KB Output is correct
59 Correct 9 ms 12372 KB Output is correct
60 Correct 11 ms 12500 KB Output is correct
61 Correct 64 ms 12628 KB Output is correct
62 Execution timed out 5022 ms 34196 KB Time limit exceeded
63 Halted 0 ms 0 KB -