Submission #1214111

#TimeUsernameProblemLanguageResultExecution timeMemory
1214111PenguinsAreCuteTourism (JOI23_tourism)C++17
0 / 100
0 ms324 KiB
#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() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> h(n,0), pre(n), euler(n), c(m);
	vector<vector<int>> adj(n);

	REP(i,1,n) {
		int a, b;
		cin >> a >> b;
		adj[a-1].push_back(b-1);
		adj[b-1].push_back(a-1);
	}

	vector<vector<int>> sparse(17,vector<int>(n,0));
	auto dfs = [cnt1=0,cnt2=0,&sparse,&adj,&h,&pre,&euler](auto &self, int x, int p) mutable -> void {
		pre[x] = cnt1++;
		sparse[0][euler[x] = cnt2++] = h[x];
		for(auto i: adj[x])
			if(i != p) {
				h[i] = h[x] + 1;
				self(self, i, x);
				sparse[0][cnt2++] = h[x];
			}
	};
	for(int i=1;i<17;i++)
		for(int j=0;j<=n-(1<<i);j++)
			sparse[i][j] = min(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);

	auto lca = [&sparse,&euler](int a, int b) {
		a = euler[a], b = euler[b];
		if(a > b)
			swap(a, b);
		int l = 31 ^ __builtin_clz(b - a + 1);
		return min(sparse[l][a], sparse[l][b-(1<<l)+1]);
	};


	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 += lca(next(it)->second,prev(s.end())->second);
			ans -= lca(it->second,prev(s.end())->second);
			ans -= lca(it->second,next(it)->second);
		} else if(it == prev(s.end())) {
			ans += lca(prev(it)->second,s.begin()->second);
			ans -= lca(it->second,s.begin()->second);
			ans -= lca(it->second,prev(it)->second);
		} else {
			ans += lca(prev(it)->second,next(it)->second);
			ans -= lca(it->second,next(it)->second);
			ans -= 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[0]/300)&1?a[1]<b[1]: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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...