Submission #1214102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214102		PenguinsAreCute	Tourism (JOI23_tourism)	C++17	28 / 100	5093 ms	3776 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v),end(v)
#define REP(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 1e5 + 5;
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> x(n,0), d(n,0), h(n,0), j(n,0), pre(n,1), ord(n-1), c(m);

	REP(i,1,n) {
		int a, b;
		cin >> a >> b;
		d[--a]++;
		d[--b]++;
		x[a]^=b;
		x[b]^=a;
	}

	int cnt = 0;
	d[0] = 0;
	REP(i,0,n)
		for(int k=i;d[k]==1;k=x[k]) {
			ord[cnt++] = k;
			d[k]--;
			d[x[k]]--;
			x[x[k]] ^= k;
			pre[x[k]] += pre[k];
		}
	h[0] = j[0] = 0;
	while(cnt--) {
		int k = ord[cnt];
		h[k] = h[x[k]] + 1;
		pre[x[k]] -= exchange(pre[k], pre[x[k]]);
		j[k] = (h[j[j[x[k]]]]+h[x[k]]==h[j[x[k]]]*2?j[j[x[k]]]:x[k]);
	}

	auto lca = [&h,&j,&x](int a, int b) {
		if(h[a] > h[b])
			swap(a, b);
		while(h[b] > h[a])
			b = (h[j[b]] >= h[a] ? j[b] : x[b]);
		while(a != b) {
			if(j[a] == j[b])
				a = x[a], b = x[b];
			else
				a = j[a], b = j[b];
		}
		return a;
	};


	REP(i,0,m) {
		cin >> c[i];
		c[i]--;
	}

	while(q--) {
		int l, r;
		cin >> l >> r;
		vector<int> v;
		for(int i=l-1;i<r;i++)
			v.push_back(c[i]);
		sort(v.begin(),v.end(),[&pre](int a, int b) {return pre[a] < pre[b];});
		long long ans = 1;
		for(auto i: v)
			ans += h[i];
		for(int i=0;i<int(v.size())-1;i++)
			ans -= h[lca(v[i],v[i+1])];
		ans -= h[lca(v[0],v.back())];
		cout << ans << "\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