Submission #753632

#	Time	Username	Problem	Language	Result	Execution time	Memory
753632		amirhoseinfar1385	Synchronization (JOI13_synchronization)	C++17	20 / 100	8074 ms	218144 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
struct yal{
	vector<pair<int,int>>w,dp,link;
	int u,v;
	int getad(int fu){
		int ret=(u^v^fu);
		return ret;
	}
};
yal alled[maxn];
vector<int>adj[maxn],fake,bal[maxn],khod[maxn];
int fn,n,m,res[maxn],vis[maxn],sz[maxn],azb[maxn],high[maxn],timea,q,par[maxn];
vector<pair<int,pair<int,int>>>fakea;
pair<int,int>stf[maxn];
int kaf=(1<<19);

struct segment{
	set<pair<int,int>> seg[(1<<20)];
	vector<int>v;
	void clear(){
		for(auto x:v){
			seg[x].clear();
		}
		v.clear();
	}
	void upd(int i,int l,int r,int tl,int tr,int av,int dov=-1){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			v.push_back(i);
			/*if(dov==-1){
				if(high[seg[i]]<high[av]){
					seg[i]=av;
				}
			}
			else{
				if(seg[i]==av){
					seg[i]=dov;
				}
			}*/
			if(dov==-1){
				seg[i].insert(make_pair(high[av],av));
			}
			else{
				seg[i].erase(make_pair(high[av],av));
			}
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,av,dov);
		upd((i<<1)^1,m+1,r,tl,tr,av,dov);
		return ;
	}
	int pors(int i){
		if(i==0){
			return 0;
		}
		int ret=pors((i>>1));
		if((int)seg[i].size()>0&&high[ret]<(*seg[i].rbegin()).first){
			ret=(*seg[i].rbegin()).second;
		}
		return ret;
	}
}seg;

void dfs(int u,int para=0,int az=0){
	fake.push_back(u);
	high[u]=high[para]+1;
	azb[u]=az;
	sz[u]=1;
	if(para==0){
		high[u]=1;
		timea=0;
	}
	else{
		sz[u]+=(int)alled[par[u]].w.size();
	}
	timea++;
	stf[u].first=timea;
	for(auto xx:adj[u]){
		int x=alled[xx].getad(u);
		if(vis[x]==1||x==para){
			continue;
		}
		par[x]=xx;
		if(para==0){
			bal[x].clear();
			dfs(x,u,x);
		}
		else{
			dfs(x,u,az);
		}
		sz[u]+=sz[x];
	}
	stf[u].second=timea;
}

int finds(int u,int para=0){
	for(auto xx:adj[u]){
		int x=alled[xx].getad(u);
		if(vis[x]==0&&x!=para&&sz[x]*2>fn){
			return finds(x,u);
		}
	}
	return u;
}

bool cmp(pair<int,pair<int,int>> a,pair<int,pair<int,int>>b){
	if(a.first!=b.first){
		return a.first<b.first;
	}
	if(a.second.second!=b.second.second){
		return a.second.second<b.second.second;
	}
	if(a.second.second==1){
		return high[a.second.first]<high[b.second.first];
	}
	else{
		return high[a.second.first]>high[b.second.first];
	}
}

void solve(int u){
	dfs(u);
	fake.clear();
	fn=sz[u];
	int v=finds(u);
	fake.clear();
	dfs(v);	
	seg.clear();
	fakea.clear();
	for(auto x:fake){
		if(x==v){
			continue;
		}
		alled[par[x]].link.clear();
		for(auto y:alled[par[x]].w){
			fakea.push_back(make_pair(y.first,make_pair(x,1)));	
			fakea.push_back(make_pair(y.second,make_pair(x,2)));
		}
	}
	sort(fakea.begin(),fakea.end(),cmp);
	for(auto x:fake){
		seg.upd(1,0,kaf-1,stf[x].first+1,stf[x].second,x);
	}
	for(int i=0;i<(int)fakea.size();i++){
		int p=seg.pors(kaf+stf[fakea[i].second.first].first);
		if(fakea[i].second.second==1){
			alled[par[fakea[i].second.first]].link.push_back(make_pair(p,v));
			int ba=p;
			seg.upd(1,0,kaf-1,stf[fakea[i].second.first].first+1,stf[fakea[i].second.first].second,fakea[i].second.first,ba);
		}
		else{
			alled[par[fakea[i].second.first]].link.back().second=p;
			seg.upd(1,0,kaf-1,stf[fakea[i].second.first].first+1,stf[fakea[i].second.first].second,fakea[i].second.first);
		}
	}
	for(auto x:fake){
		if(x==v){
			khod[v].push_back(0);
			continue;
		}
		for(int i=0;i<(int)alled[par[x]].w.size();i++){
			int linky1=alled[par[x]].link[i].first;
			int p=lower_bound(alled[par[linky1]].w.begin(),alled[par[linky1]].w.end(),make_pair(alled[par[x]].w[i].first,-1))-alled[par[linky1]].w.begin();
			if(linky1==v){
				alled[par[x]].dp[i].first=alled[par[x]].w[i].first;
			}
			else if(p==alled[par[linky1]].w.size()){
				alled[par[x]].dp[i].first=m+10;
			}
			else{
				alled[par[x]].dp[i].first=alled[par[linky1]].dp[p].first;
			}
			int linky2=alled[par[x]].link[i].second;
			p=lower_bound(alled[par[linky2]].w.begin(),alled[par[linky2]].w.end(),make_pair(alled[par[x]].w[i].second,-1))-alled[par[linky2]].w.begin();
			p--;
			if(linky2==v){
				alled[par[x]].dp[i].second=alled[par[x]].w[i].second;
			}
			else if(p<0){
				alled[par[x]].dp[i].second=-1;
			}
			else{
				alled[par[x]].dp[i].second=alled[par[linky2]].dp[p].second;
			}
		}
		if(alled[par[x]].w.size()==0){
			continue;
		}
		int ff=alled[par[x]].dp[0].first;
		if(ff>m+2){
			continue;
		}
		khod[v].push_back(ff);
		bal[azb[x]].push_back(ff);
	}
	sort(khod[v].begin(),khod[v].end());
	for(auto xx:adj[v]){
		int x=alled[xx].getad(v);
		if(vis[x]==0){
			sort(bal[x].begin(),bal[x].end());
		}
	}
	for(auto x:fake){
		if(x==v){
			res[x]+=khod[v].size();
			continue;
		}
		if((int)alled[par[x]].w.size()==0){
			continue;
		}
		int ff=alled[par[x]].dp.back().second;
		int p=upper_bound(khod[v].begin(),khod[v].end(),ff)-khod[v].begin();
		p--;
		res[x]+=p+1;
		p=upper_bound(bal[azb[x]].begin(),bal[azb[x]].end(),ff)-bal[azb[x]].begin();
		p--;
		res[x]-=p+1;
	}
	vis[v]=1;
	for(auto xx:adj[v]){
		int x=alled[xx].getad(v);
		if(vis[x]==0){
			solve(x);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=n-1;i++){
		cin>>alled[i].u>>alled[i].v;
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int u;
		cin>>u;
		if((int)alled[u].w.size()==0||alled[u].w.back().second!=-1){
			alled[u].w.push_back(make_pair(i,-1));
		}
		else{
			alled[u].w.back().second=i;
		}
	}
	for(int i=1;i<n;i++){
		if((int)alled[i].w.size()>0&&alled[i].w.back().second==-1){
			alled[i].w.back().second=m+1;
		}
		alled[i].dp.resize((int)alled[i].w.size());
	}
	solve(1);
	for(int i=0;i<q;i++){
		int u;
		cin>>u;
		cout<<res[u]<<"\n";
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'void solve(int)':
synchronization.cpp:172:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |    else if(p==alled[par[linky1]].w.size()){
      |            ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40