Submission #1214562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214562		siewjh	Tourism (JOI23_tourism)	C++20	100 / 100	660 ms	21828 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int nodes, spots, queries;
int p[MAXN], d[MAXN], heavy[MAXN], head[MAXN], st[MAXN], fw[MAXN], ans[MAXN], pid = 0;
vector<int> adj[MAXN];
vector<pair<int, int>> qv[MAXN];
set<pair<int, int>> vs;
int dfs(int x, int par, int dep){
	p[x] = par; d[x] = dep;
	int sz = 1, msz = 0;
	for (int nn : adj[x]){
		if (nn == par) continue;
		int ssz = dfs(nn, x, dep + 1);
		sz += ssz;
		if (ssz > msz){
			msz = ssz; heavy[x] = nn;
		}
	}
	return sz;
}
void decomp(int x, int h){
	head[x] = h; st[x] = ++pid;
	if (heavy[x] != -1) decomp(heavy[x], h);
	for (int nn : adj[x]){
		if (nn == p[x] || nn == heavy[x]) continue;
		decomp(nn, nn);
	}
}
void update(int x, int v){
	while (x <= spots){
		fw[x] += v;
		x += (x & (-x));
	}
}
int query(int x){
	int res = 0;
	while (x){
		res += fw[x];
		x -= (x & (-x));
	}
	return res;
}
void insert(int l, int r, int v){
	auto it = prev(vs.lower_bound({l + 1, -1}));
	while (1){
		int lh = it->first, rh = next(it)->first - 1, vh = it->second;
		update(vh, -(min(r, rh) - max(l, lh) + 1));
		if (lh < l){
			if (rh >= r){
				if (rh > r) vs.insert({r + 1, vh});
				break;
			}
			it++;
		}
		else{
			it = vs.erase(it);
			if (rh >= r){
				if (rh > r) vs.insert({r + 1, vh});
				break;
			}
		}
	}
	vs.insert({l, v}); update(v, r - l + 1);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	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);
	}
	memset(heavy, -1, sizeof(heavy));
	dfs(1, -1, 0); decomp(1, 1);
	vector<int> spv(spots + 1);
	for (int i = 1; i <= spots; i++) cin >> spv[i];
	for (int i = 0; i < queries; i++){
		int l, r; cin >> l >> r;
		qv[l].push_back({r, i});
	}
	vs.insert({1, MAXN}); vs.insert({nodes + 1, -1});
	for (int l = spots; l >= 1; l--){
		if (l != spots){
			int a = spv[l], b = spv[l + 1];
			for (; head[a] != head[b]; b = p[head[b]]){
				if (d[head[a]] > d[head[b]]) swap(a, b);
				insert(st[head[b]], st[b], l + 1);
			}
			if (a != b){
				if (d[a] > d[b]) swap(a, b);
				insert(st[a] + 1, st[b], l + 1);
			}
		}
		for (auto [r, id] : qv[l]) ans[id] = query(r) + 1;
	}
	for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}

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