Submission #1214108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214108		PenguinsAreCute	Tourism (JOI23_tourism)	C++17	28 / 100	5091 ms	7860 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++)
using ii = pair<int,int>;
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]--;
	}

	multiset<ii> s;
	auto val = [&s,&h,&lca](set<ii>::iterator it) {
		if(s.size() == 1)
			return 0;
		int ans = h[it->second];
		if(it == s.begin()) {
			ans += h[lca(next(it)->second,prev(s.end())->second)];
			ans -= h[lca(it->second,prev(s.end())->second)];
			ans -= h[lca(it->second,next(it)->second)];
		} else if(it == prev(s.end())) {
			ans += h[lca(prev(it)->second,s.begin()->second)];
			ans -= h[lca(it->second,s.begin()->second)];
			ans -= h[lca(it->second,prev(it)->second)];
		} else {
			ans += h[lca(prev(it)->second,next(it)->second)];
			ans -= h[lca(it->second,next(it)->second)];
			ans -= h[lca(it->second,prev(it)->second)];
		}
		return ans;
	};
	auto ins = [&s,&val](ii x) -> int {
		auto it = s.insert(x);
		return val(it);
	};
	auto rem = [&s,&val](ii x) -> int {
		auto it = s.find(x);
		int ans = -val(it);
		s.erase(it);
		return ans;
	};

	auto qry = [cl=0,cr=-1,ans=1,&c,&pre,&ins,&rem](int ql, int qr) mutable -> int {
		while(cr < qr) {
			cr++;
			ans += ins({pre[c[cr]],c[cr]});
		}
		while(cl > ql) {
			cl--;
			ans += ins({pre[c[cl]],c[cl]});
		}
		while(cr > qr) {
			ans += rem({pre[c[cr]],c[cr]});
			cr--;
		}
		while(cl < ql) {
			ans += rem({pre[c[cl]],c[cl]});
			cl++;
		}
		return ans;
	};

	vector<array<int,3>> qrs(q);
	REP(i,0,q) {
		cin >> qrs[i][0] >> qrs[i][1];
		qrs[i][0]--;
		qrs[i][1]--;
		qrs[i][2] = i;
	}
	sort(all(qrs),[](array<int,3> a, array<int,3> b) {
		if(a[0]/300 == b[0]/300)
			return a[1]<b[1];
		return a[0]<b[0];
	});
	vector<int> ans(q);
	REP(i,0,q)
		ans[qrs[i][2]] = qry(qrs[i][0], qrs[i][1]);
	for(int i=0;i<q;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