Submission #1214147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214147		siewjh	Tourism (JOI23_tourism)	C++20	28 / 100	5094 ms	25400 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int p[18][MAXN], d[MAXN], ord[MAXN], rord[MAXN], sps[18][MAXN], ans[MAXN], oid = 0, clca, lid, rid, val;
vector<int> adj[MAXN];
multiset<int> sord;
void dfs(int x, int par, int dep){
	p[0][x] = par; d[x] = dep; ord[x] = ++oid; rord[oid] = x;
	for (int nn : adj[x]){
		if (nn == par) continue;
		dfs(nn, x, dep + 1);
	}
}
int lca(int a, int b){
	if (d[a] > d[b]) swap(a, b);
	for (int k = 17; k >= 0; k--)
		if (d[b] - (1 << k) >= d[a])
			b = p[k][b];
	if (a == b) return a;
	for (int k = 17; k >= 0; k--)
		if (p[k][a] != p[k][b]){
			a = p[k][a]; b = p[k][b];
		}
	return p[0][a];
}
int query(int l, int r){
	int k = log2(r - l + 1);
	return lca(sps[k][l], sps[k][r - (1 << k) + 1]);
}
void add(int x){
	auto it = sord.lower_bound(ord[x]);
	int lcad = -1;
	if (it != sord.end()) lcad = max(lcad, d[lca(x, rord[*it])]);
	if (it != sord.begin()) lcad = max(lcad, d[lca(x, rord[*prev(it)])]);
	sord.insert(ord[x]);
	val += d[x] - lcad;
	int nlca = query(lid, rid);
	if (nlca != clca){
		val += d[clca] - d[nlca];
		clca = nlca;
	}
}
void rem(int x){
	sord.erase(sord.find(ord[x]));
	auto it = sord.lower_bound(ord[x]);
	int lcad = -1;
	if (it != sord.end()) lcad = max(lcad, d[lca(x, rord[*it])]);
	if (it != sord.begin()) lcad = max(lcad, d[lca(x, rord[*prev(it)])]);
	val -= d[x] - lcad;
	int nlca = query(lid, rid);
	if (nlca != clca){
		val -= d[nlca] - d[clca];
		clca = nlca;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nodes, spots, queries; cin >> nodes >> spots >> queries;
	for (int i = 1; i < nodes; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dfs(1, -1, 0);
	for (int k = 1; k <= 17; k++)
		for (int i = 1; i <= nodes; i++){
			if (p[k - 1][i] == -1) p[k][i] = -1;
			else p[k][i] = p[k - 1][p[k - 1][i]];
		}
	vector<int> spv(spots + 1);
	for (int i = 1; i <= spots; i++) cin >> spv[i];
	for (int i = 1; i <= spots; i++) sps[0][i] = spv[i];
	for (int k = 1; k <= 17; k++)
		for (int i = spots - (1 << k) + 1; i >= 1; i--)
			sps[k][i] = lca(sps[k - 1][i], sps[k - 1][i + (1 << (k - 1))]);
	vector<tuple<int, int, int, int>> vq(queries);
	int bsz = 320;
	for (int i = 0; i < queries; i++){
		int l, r; cin >> l >> r;
		vq[i] = {r / bsz, l, r, i};
	}
	sort(vq.begin(), vq.end());
	clca = spv[1]; lid = rid = 1; val = 1;
	sord.insert(ord[spv[1]]);
	for (auto [rb, l, r, id] : vq){
		while (rid < r){
			rid++; add(spv[rid]);
		}
		while (lid > l){
			lid--; add(spv[lid]);
		}
		while (rid > r){
			rid--; rem(spv[rid + 1]);
		}
		while (lid < l){
			lid++; rem(spv[lid - 1]);
		}
		ans[id] = val;
	}
	for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41