oj.uz

Submission #743873

# Submission time Handle Problem Language Result Execution time Memory
743873 2023-05-18T05:41:40 Z pavement Tourism (JOI23_tourism) C++17
18 / 100
 5000 ms 26740 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 = 3;
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;

void dfs(int n, int e = -1) {
	pre[n] = ++idx;
	for (int k = 1; k <= 20; 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 = 20; k >= 0; k--) {
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	}
	if (u == v) return u;
	for (int k = 20; 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) {
	int w = lca(u, v);
	return dep[u] + dep[v] - 2 * dep[w];
}

void add_path(int u, int v) {
	//~ cout << " + " << u << ' ' << v << '\n';
	cur += dist(u, v);
}

void rem_path(int u, int v) {
	//~ cout << " - " << u << ' ' << v << '\n';
	cur -= dist(u, v);	
}

void add(int k) {
	//~ cout << "ADD " << k << '\n';
	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;
	//~ cout << "! " << x.second << ' ' << y.second << '\n';
	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(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;
		}
		//~ cout << "@  " << L[i] << ' ' << R[i] << '\n';
		// move window to [L[i], R[i]]
		if (wR == -1 || wL / BLK_SZ != L[i] / BLK_SZ) {
			for (int j = wL; j <= wR; j++) rem(C[j]);
			cur = 0;
			//~ cout << "REM ALL " << cur << '\n';
			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]);
			//~ cout << cur << ' ' << get<0>(diam) << ' ' << get<1>(diam) << ' ' << get<2>(diam) << '\n';
			out[idx] = cur / 2 + 1;
			//~ cout << cur / 2 + 1 << '\n';
			for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
			cur = sv_cur;
			wL = L[i];
			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;
		//~ cout << cur / 2 + 1 << '\n';
		for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
		cur = sv_cur;
		wL = L[i];
		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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12608 KB Output is correct
2 Correct 6 ms 12468 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 10 ms 12540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12608 KB Output is correct
2 Correct 6 ms 12468 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 10 ms 12540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12472 KB Output is correct
2 Correct 8 ms 12500 KB Output is correct
3 Correct 95 ms 12648 KB Output is correct
4 Execution timed out 5057 ms 26740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 73 ms 15896 KB Output is correct
3 Correct 104 ms 16204 KB Output is correct
4 Correct 88 ms 16688 KB Output is correct
5 Correct 219 ms 23000 KB Output is correct
6 Correct 215 ms 19948 KB Output is correct
7 Correct 212 ms 18768 KB Output is correct
8 Correct 215 ms 18724 KB Output is correct
9 Correct 192 ms 18404 KB Output is correct
10 Correct 205 ms 18488 KB Output is correct
11 Correct 194 ms 18384 KB Output is correct
12 Correct 165 ms 18464 KB Output is correct
13 Correct 157 ms 18700 KB Output is correct
14 Correct 144 ms 19384 KB Output is correct
15 Correct 108 ms 22268 KB Output is correct
16 Correct 192 ms 20848 KB Output is correct
17 Correct 174 ms 20872 KB Output is correct
18 Correct 177 ms 20932 KB Output is correct
19 Correct 246 ms 23000 KB Output is correct
20 Correct 166 ms 21164 KB Output is correct
21 Correct 173 ms 19536 KB Output is correct
22 Correct 195 ms 18884 KB Output is correct
23 Correct 222 ms 18796 KB Output is correct
24 Correct 229 ms 18472 KB Output is correct
25 Correct 259 ms 18824 KB Output is correct
26 Correct 297 ms 18500 KB Output is correct
27 Correct 272 ms 18392 KB Output is correct
28 Correct 254 ms 18844 KB Output is correct
29 Correct 279 ms 18844 KB Output is correct
30 Correct 272 ms 18856 KB Output is correct
31 Correct 246 ms 18920 KB Output is correct
32 Correct 218 ms 19300 KB Output is correct
33 Correct 141 ms 20716 KB Output is correct
34 Correct 98 ms 22072 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 8 ms 12480 KB Output is correct
3 Correct 93 ms 12648 KB Output is correct
4 Execution timed out 5074 ms 23772 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 12608 KB Output is correct
2 Correct 6 ms 12468 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Incorrect 10 ms 12540 KB Output isn't correct
5 Halted 0 ms 0 KB -