Submission #1214123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214123		emptypringlescan	Tourism (JOI23_tourism)	C++17	100 / 100	2124 ms	47220 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
const int buc=360;
int n,m,q;
vector<int> adj[100005];
pair<pair<int,int>,pair<int,int> > qu[100005];
int arr[100005];
pair<int,int> srt[100005];
int pre[100005],dep[100005];
vector<int> eul;
pair<int,int> sparse[20][200005];
void build(){
	for(int i=0; i<(int)eul.size(); i++) sparse[0][i]={pre[eul[i]],eul[i]};
	for(int i=1; i<20; i++){
		int sz=1<<(i-1);
		for(int j=0; j<(int)eul.size(); j++){
			if(j+sz+sz>(int)eul.size()) break;
			sparse[i][j]=min(sparse[i-1][j],sparse[i-1][j+sz]);
		}
	}
}
int lca(int a, int b){
	int x=pre[a],y=pre[b];
	if(x>y) swap(x,y);
	int bt=31-__builtin_clz(y-x+1);
	int sz=1<<bt;
	assert(sz<=y-x+1&&sz+sz>=y-x+1);
	return min(sparse[bt][x],sparse[bt][y-sz+1]).second;
}
int dis(int a, int b){
	int c=lca(a,b);
	//cout << a << "e" << b << "e" << c << '\n';
	//cout << dep[a]+dep[b]-2*dep[c] << '\n';
	return dep[a]+dep[b]-2*dep[c];
}
void dfs(int x, int p){
	pre[x]=(int)eul.size();
	eul.push_back(x);
	for(int i:adj[x]) if(i!=p){
		dep[i]=dep[x]+1;
		dfs(i,x);
		eul.push_back(x);
	}
}
int lnk[2][100005];
int auxsz;
vector<pair<pair<int,pair<int,int> >,int> > undo;
void del(int x){
	int prv=lnk[1][x],nxt=lnk[0][x];
	int nsz=auxsz;
	nsz-=dis(arr[prv],arr[x]);
	nsz-=dis(arr[x],arr[nxt]);
	nsz+=dis(arr[prv],arr[nxt]);
	//cout << prv << ' ' << x << ' ' << nxt << '\n';
	//cout << dis(arr[prv],arr[x]) << ' ' << dis(arr[x],arr[nxt]) << ' ' << dis(arr[prv],arr[nxt]) << '\n';
	//cout << x << " ok " << nsz << '\n';
	lnk[0][prv]=nxt;
	lnk[1][nxt]=prv;
	undo.push_back({{x,{prv,nxt}},auxsz});
	auxsz=nsz;
}
void rbd(){
	assert(!undo.empty());
	auto x=undo.back();
	undo.pop_back();
	//cout << x.first.second.first << ' ' << x.first.second.second << '\n';
	lnk[0][x.first.second.first]=x.first.first;
	lnk[1][x.first.second.second]=x.first.first;
	auxsz=x.second;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1,-1);
	build();
	for(int i=1; i<=m; i++) cin >> arr[i],srt[i]={pre[arr[i]],i};
	sort(srt+1,srt+m+1);
	for(int i=1; i<m; i++) lnk[0][srt[i].second]=srt[i+1].second;
	lnk[0][srt[m].second]=srt[1].second;
	lnk[1][srt[1].second]=srt[m].second;
	for(int i=2; i<=m; i++) lnk[1][srt[i].second]=srt[i-1].second;
	for(int i=1; i<m; i++){
		auxsz+=dis(arr[srt[i].second],arr[srt[i+1].second]);
	}
	auxsz+=dis(arr[srt[m].second],arr[srt[1].second]);
	//cout << auxsz << '\n';
	for(int i=0; i<q; i++){
		int a,b;
		cin >> a >> b;
		qu[i]={{a/buc,-b},{i,a}};
	}
	sort(qu,qu+q);
	int c1=1,c2=m,un1=0,un2=0;
	int ans[q];
	for(int i=0; i<q; i++){
		if(i&&qu[i].first.first!=qu[i-1].first.first){
			while(un2){
				rbd();
				un2--;
				c2++;
			}
			while(c1<qu[i].first.first*buc){
				del(c1);
				c1++;
			}
			undo.clear();
		}
		while(c2>-qu[i].first.second){
			del(c2);
			un2++;
			c2--;
		}
		while(c1<qu[i].second.second){
			del(c1);
			un1++;
			c1++;
		}
		//cout << c1 << ' ' << c2 << ' ' << auxsz << '\n';
		ans[qu[i].second.first]=auxsz/2+1;
		while(un1){
			rbd();
			c1--;
			un1--;
		}
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}

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