Submission #1214242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214242		siewjh	Tourism (JOI23_tourism)	C++20	0 / 100	880 ms	1114112 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int p[18][MAXN], d[MAXN], ord[MAXN], en[MAXN], rord[MAXN], spv[MAXN], ans[MAXN], oid = 0;
int st2[MAXN], en2[MAXN], rord2[MAXN], oid2;
int lsum[MAXN];
vector<int> adj[MAXN];
vector<pair<int, int>> adj2[MAXN], rsum[MAXN], ql[MAXN];
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);
	}
	en[x] = oid;
}
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];
}
void dfs2(int x, int par){
	st2[x] = ++oid2; rord2[oid2] = x;
	for (auto [nn, nd] : adj2[x]){
		if (nn == par) continue;
		dfs2(nn, x);
	}
	en2[x] = oid2;
}
struct node{
	int s, m, e, mx;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; mx = -MAXN;
		if (s != e){
			l = new node(s, m); r = new node(m + 1, e);
		}
	}
	void update(int p, int v){
		if (s == e){
			mx = max(mx, v); return;
		}
		else if (p <= m) l->update(p, v);
		else r->update(p, v);
		mx = max(l->mx, r->mx);
	}
	int query(int x, int y){
		if (x == s && y == e) return mx;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return max(l->query(x, m), r->query(m + 1, y));
	}
} *rootl, *rootr;
struct node2{
	int s, m, e; int val;
	node2 *l, *r;
	node2 (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; val = 0;
		if (s != e){
			l = new node2(s, m); r = new node2(m + 1, e);
		}
	}
	void update(int p, int v){
		if (s == e){
			val += v; return;
		}
		else if (p <= m) l->update(p, v);
		else r->update(p, v);
		val = l->val + r->val;
	}
	int query(int x, int y){
		if (x > y) return 0;
		if (x == s && y == e) return val;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return l->query(x, m) + r->query(m + 1, y);
	}
} *root2;
void dfs3(int x, int par, int pd, int m){
	if (par != -1){
		int l, r; l = rootl->query(st2[x], en2[x]), r = -rootr->query(st2[x], en2[x]);
		//cout << x << ' ' << l << ' ' << r << endl;
		if (l != -MAXN) lsum[l] += pd;
		if (r != MAXN){
			if (l != -MAXN) rsum[l].push_back({r, pd});
			root2->update(r, pd);
		}
	}
	for (auto [nn, nd] : adj2[x]){
		if (nn == par) continue;
		dfs3(nn, x, nd, m);
	}
}
void dnc(int s, int e, vector<tuple<int, int, int>> &vq){
	if (vq.empty()) return;
	vector<tuple<int, int, int>> vqh, vql, vqr;
	int m = (s + e) >> 1;
	//cout << s << ' ' << e << ' ' << m << endl;
	for (auto [l, r, q] : vq) (r < m ? vql : (l > m ? vqr : vqh)).push_back({l, r, q});
	if (!vqh.empty()){
		vector<int> vtn;
		for (int i = s; i <= e; i++) vtn.push_back(ord[spv[i]]);
		for (int i = s + 1; i <= e; i++) vtn.push_back(ord[lca(spv[i - 1], spv[i])]);
		sort(vtn.begin(), vtn.end());
		vtn.resize(distance(vtn.begin(), unique(vtn.begin(), vtn.end())));
		vector<int> stk;
		for (int ox : vtn){
			int x = rord[ox];
			if (stk.empty()){
				stk.push_back(x); continue;
			}
			while (ox > en[stk.back()]) stk.pop_back();
			int par = stk.back(), dist = d[x] - d[par];
			adj2[x].push_back({par, dist}); adj2[par].push_back({x, dist});
			stk.push_back(x);
		}
		oid2 = 0; dfs2(spv[m], -1);
		rootl = new node(1, oid2), rootr = new node(1, oid2); root2 = new node2(m + 1, e);
		for (int i = s; i < m; i++) rootl->update(st2[spv[i]], i);
		for (int i = m + 1; i <= e; i++) rootr->update(st2[spv[i]], -i);
		dfs3(spv[m], -1, -1, m);
		for (auto [l, r, q] : vqh) ql[l].push_back({r, q});
		int res = 1;
		for (int i = m; i >= s; i--){
			res += lsum[i];
			//cout << i << ' ' << res << endl;
			for (auto [r, v] : rsum[i]) root2->update(r, -v);
			for (auto [r, q] : ql[i]){
				ans[q] = res + root2->query(m + 1, r);
				//cout << q << ' ' << ans[q] << endl;
			}
		}
		for (int i = s; i <= m; i++){
			lsum[i] = 0; rsum[i].clear(); ql[i].clear();
		}
		for (int ox : vtn) adj2[rord[ox]].clear();
	}
	if (s != e){
		dnc(s, m, vql); dnc(m + 1, e, vqr);
	}
}
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]];
		}
	for (int i = 1; i <= spots; i++) cin >> spv[i];
	vector<tuple<int, int, int>> vq(queries);
	for (int i = 0; i < queries; i++){
		int l, r; cin >> l >> r;
		vq[i] = {l, r, i};
	}
	dnc(1, spots, vq);
	for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}

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