Submission #961962

#	Time	Username	Problem	Language	Result	Execution time	Memory
961962		amirhoseinfar1385	Tourism (JOI23_tourism)	C++17	100 / 100	199 ms	37356 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=18;
int n,m,q,sz[maxn],par[maxn],parh[maxn],timea,all[maxn],res[maxn],high[maxn];
vector<int>adj[maxn];
vector<pair<int,int>>allq[maxn];
pair<int,int>stf[maxn],nag[maxn];
vector<pair<int,int>>allr[maxn];
int lca[lg][maxn],kaf=(1<<18);

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

int getlca(int u,int v){
	if(u==0){
		return v;
	}
	if(v==0){
		return u;
	}
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

struct segment{
	int seg[(1<<19)];
	void create(){
		for(int i=(1<<19)-1;i>=1;i--){
			if(i>=kaf){
				if(i-kaf<=m){
					seg[i]=all[i-kaf];
				}
			}else{
				seg[i]=getlca(seg[(i<<1)],seg[(i<<1)^1]);
			}
		}
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return getlca(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

struct fenwick{
	int fn[maxn];
	void upd(int i,int w){
		//cout<<"upd: "<<i<<" "<<w<<endl;
		i++;
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int i){
		i++;
		int ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;
	}
}fen;

void vorod(){
	cin>>n>>m>>q;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=m;i++){
		cin>>all[i];
	}
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		nag[i]=make_pair(l,r);
		allq[r].push_back(make_pair(l,i));
	}
}

void dfs1(int u=1){
	if(u==1){
		parh[u]=1;
	}
	//cout<<u<<" ";
	timea++;
	stf[u].first=timea;
	if((int)adj[u].size()==0){
		stf[u].second=timea;
		return ;
	}
	parh[adj[u][0]]=parh[u];
	dfs1(adj[u][0]);
	for(int i=1;i<(int)adj[u].size();i++){
		parh[adj[u][i]]=adj[u][i];
		dfs1(adj[u][i]);
	}
	stf[u].second=timea;
}

bool cmp(int a,int b){
	return sz[a]>sz[b];
}

void dfs(int u=1,int p=-1){
	if(p!=-1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),p));
	}
	sz[u]=1;
	for(auto x:adj[u]){
		par[x]=u;
		high[x]=high[u]+1;
		lca[0][x]=u;
		dfs(x,u);
		sz[u]+=sz[x];
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

void pre(){
	dfs();
	dfs1();
	//cout<<endl;
	callca();
	seg.create();
}

void upd(int u,int ind){
	//cout<<u<<" "<<ind<<" "<<parh[u]<<endl;
	int ph=parh[u];
	int last=stf[ph].first-1;
	while((int)allr[ph].size()>0){
		int v=allr[ph].back().first;
		if(stf[v].first<=stf[u].first){
			fen.upd(allr[ph].back().second,-(stf[v].first-last));
			last=stf[v].first;
			allr[ph].pop_back();
		}else{
			fen.upd(allr[ph].back().second,-(stf[v].first-last));
			fen.upd(allr[ph].back().second,stf[v].first-stf[u].first);
			break;
		}
	}
	fen.upd(ind,stf[u].first-stf[ph].first+1);
	allr[ph].push_back(make_pair(u,ind));
	if(ph!=1){
		upd(par[ph],ind);
	}
}

void solve(){
	for(int i=1;i<=m;i++){
		//cout<<"hey: "<<i<<" "<<all[i]<<endl;
		upd(all[i],i);
		for(auto x:allq[i]){
			res[x.second]=fen.pors(i)-fen.pors(x.first-1);
		}
	}
}

void khor(){
	for(int i=0;i<q;i++){
		res[i]-=high[seg.pors(1,0,kaf-1,nag[i].first,nag[i].second)];
		//cout<<"injy: "<<seg.pors(1,0,kaf-1,nag[i].first,nag[i].second)<<" "<<high[seg.pors(1,0,kaf-1,nag[i].first,nag[i].second)]<<"\n";
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

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