oj.uz

Submission #753732

# Submission time Handle Problem Language Result Execution time Memory
753732 2023-06-05T19:29:29 Z amirhoseinfar1385 Synchronization (JOI13_synchronization) C++17
100 / 100
 1782 ms 70628 KB 
#undef _GLIBCXX_DEBUG               
#pragma GCC optimize("Ofast,inline") 

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                    
#pragma GCC target("movbe")                                
#pragma GCC target("aes,pclmul,rdrnd")
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+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];
pair<int,int>stf[maxn];
int kaf=(1<<18);
struct segment{
	int seg[(1<<19)];
	vector<pair<int,int>>v;
	void back(int len){
		while((int)v.size()>len){
			seg[v.back().first]=v.back().second;
			v.pop_back();
		}
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			v.push_back(make_pair(i,seg[i]));
			seg[i]=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	int pors(int i){
		if(i==0){
			return 0;
		}
		int ret=pors((i>>1));
		if(high[seg[i]]>high[ret]){
			ret=seg[i];
		}
		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;
}
void calalllink(int u,int para=0){
	int fl=(int)seg.v.size();
	if(para==0){
		seg.upd(1,0,kaf-1,1,m+5,u);
	}
	else{
		alled[par[u]].link.clear();
		alled[par[u]].link.resize((int)alled[par[u]].w.size());
		for(int i=0;i<(int)alled[par[u]].w.size();i++){
			alled[par[u]].link[i].first=seg.pors(kaf+alled[par[u]].w[i].first);
			alled[par[u]].link[i].second=seg.pors(kaf+alled[par[u]].w[i].second);
		//	cout<<u<<" "<<alled[par[u]].link[i].first<<" "<<alled[par[u]].link[i].second<<" "<<alled[par[u]].w[i].first<<" "<<alled[par[u]].w[i].second<<"\n";
		}
		if((int)alled[par[u]].w.size()>0){
			seg.upd(1,0,kaf-1,1,alled[par[u]].w[0].first-1,u);
			seg.upd(1,0,kaf-1,alled[par[u]].w.back().second+1,m+5,u);
			for(int i=1;i<(int)alled[par[u]].w.size();i++){
				seg.upd(1,0,kaf-1,alled[par[u]].w[i-1].second+1,alled[par[u]].w[i].first-1,u);
			}
		}
		else{
			seg.upd(1,0,kaf-1,1,m+5,u);
		}
	}
	for(auto xx:adj[u]){
		int x=alled[xx].getad(u);
		if(vis[x]==0&&x!=para){
			calalllink(x,u);
		}
	}
	seg.back(fl);
}
 
void solve(int u){
	dfs(u);
	fake.clear();
	fn=sz[u];
	int v=finds(u);
	fake.clear();
	dfs(v);	
	calalllink(v);
	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==(int)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";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 9 ms 15244 KB Output is correct
3 Correct 8 ms 15188 KB Output is correct
4 Correct 8 ms 15228 KB Output is correct
5 Correct 9 ms 15168 KB Output is correct
6 Correct 13 ms 15468 KB Output is correct
7 Correct 88 ms 17512 KB Output is correct
8 Correct 86 ms 17488 KB Output is correct
9 Correct 112 ms 17528 KB Output is correct
10 Correct 1404 ms 38396 KB Output is correct
11 Correct 1469 ms 38424 KB Output is correct
12 Correct 1770 ms 60156 KB Output is correct
13 Correct 242 ms 38212 KB Output is correct
14 Correct 1236 ms 44192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 56984 KB Output is correct
2 Correct 723 ms 56264 KB Output is correct
3 Correct 1237 ms 69960 KB Output is correct
4 Correct 1195 ms 69152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 9 ms 15188 KB Output is correct
3 Correct 8 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 10 ms 15188 KB Output is correct
6 Correct 20 ms 15724 KB Output is correct
7 Correct 132 ms 19704 KB Output is correct
8 Correct 1751 ms 60480 KB Output is correct
9 Correct 1782 ms 60280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1755 ms 60524 KB Output is correct
2 Correct 1217 ms 70264 KB Output is correct
3 Correct 1231 ms 70492 KB Output is correct
4 Correct 1260 ms 70628 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15244 KB Output is correct
2 Correct 10 ms 15148 KB Output is correct
3 Correct 10 ms 15164 KB Output is correct
4 Correct 11 ms 15188 KB Output is correct
5 Correct 15 ms 15520 KB Output is correct
6 Correct 90 ms 17616 KB Output is correct
7 Correct 1466 ms 38872 KB Output is correct
8 Correct 1782 ms 60316 KB Output is correct
9 Correct 272 ms 38708 KB Output is correct
10 Correct 1402 ms 44716 KB Output is correct
11 Correct 763 ms 57660 KB Output is correct
12 Correct 764 ms 57680 KB Output is correct
13 Correct 1216 ms 70484 KB Output is correct