oj.uz

Submission #753731

# Submission time Handle Problem Language Result Execution time Memory
753731 2023-06-05T19:27:42 Z amirhoseinfar1385 Synchronization (JOI13_synchronization) C++17
100 / 100
 1755 ms 70600 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,inline")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
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 8 ms 15236 KB Output is correct
3 Correct 9 ms 15188 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 9 ms 15188 KB Output is correct
6 Correct 13 ms 15380 KB Output is correct
7 Correct 88 ms 17484 KB Output is correct
8 Correct 84 ms 17448 KB Output is correct
9 Correct 88 ms 17504 KB Output is correct
10 Correct 1416 ms 38720 KB Output is correct
11 Correct 1464 ms 38516 KB Output is correct
12 Correct 1698 ms 60200 KB Output is correct
13 Correct 249 ms 38208 KB Output is correct
14 Correct 1195 ms 44124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 57124 KB Output is correct
2 Correct 716 ms 56296 KB Output is correct
3 Correct 1171 ms 69860 KB Output is correct
4 Correct 1105 ms 69064 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 9 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 8 ms 15204 KB Output is correct
6 Correct 15 ms 15700 KB Output is correct
7 Correct 121 ms 19724 KB Output is correct
8 Correct 1742 ms 60368 KB Output is correct
9 Correct 1755 ms 60408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1701 ms 60328 KB Output is correct
2 Correct 1199 ms 70272 KB Output is correct
3 Correct 1164 ms 70572 KB Output is correct
4 Correct 1212 ms 70600 KB Output is correct

Subtask #5
40.0 / 40.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 7 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 13 ms 15516 KB Output is correct
6 Correct 92 ms 17524 KB Output is correct
7 Correct 1485 ms 38908 KB Output is correct
8 Correct 1745 ms 60492 KB Output is correct
9 Correct 285 ms 38852 KB Output is correct
10 Correct 1226 ms 44704 KB Output is correct
11 Correct 731 ms 57680 KB Output is correct
12 Correct 740 ms 57628 KB Output is correct
13 Correct 1168 ms 70564 KB Output is correct