Submission #1214137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214137		PenguinsAreCute	Tourism (JOI23_tourism)	C++17	28 / 100	5095 ms	31284 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++)
#pragma GCC optimize("O3")
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), 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(18,vector<int>(2*n,0));
	auto dfs = [cnt=0,&sparse,&adj,&h,&euler](auto &self, int x, int p) mutable -> void {
		sparse[0][euler[x] = cnt++] = h[x];
		for(auto i: adj[x])
			if(i != p) {
				h[i] = h[x] + 1;
				self(self, i, x);
				sparse[0][cnt++] = h[x];
			}
	};
	dfs(dfs, 0, -1);
	for(int i=1;i<18;i++)
		for(int j=0;j<=2*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) {
		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()) {
			int r1 = lca(next(it)->first,prev(s.end())->first);
			int r2 = lca(it->first,next(it)->first);
			ans += r1 - r2 - min(r1, r2);
		} else if(it == prev(s.end())) {
			int r1 = lca(prev(it)->first,s.begin()->first);
			int r2 = lca(it->first,prev(it)->first);
			ans += r1 - r2 - min(r1, r2);
		} else {
			int r1 = lca(it->first,next(it)->first);
			int r2 = lca(it->first,prev(it)->first);
			ans += min(r1, r2) - r1 - r2;
		}
		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,&euler,&ins,&rem](int ql, int qr) mutable -> int {
		while(cr < qr) {
			cr++;
			ans += ins({euler[c[cr]],c[cr]});
		}
		while(cl > ql) {
			cl--;
			ans += ins({euler[c[cl]],c[cl]});
		}
		while(cr > qr) {
			ans += rem({euler[c[cr]],c[cr]});
			cr--;
		}
		while(cl < ql) {
			ans += rem({euler[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";
}

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