oj.uz

Submission #753730

# Submission time Handle Problem Language Result Execution time Memory
753730 2023-06-05T19:24:34 Z amirhoseinfar1385 Synchronization (JOI13_synchronization) C++17
100 / 100
 3425 ms 95516 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
	vector<pair<int,int>>w,dp;
	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{
	pair<int,int> seg[(1<<19)];
	vector<pair<int,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,pair<int,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 ;
	}
	pair<int,int> pors(int i){
		if(i==0){
			return make_pair(0,0);
		}
		pair<int,int> ret=pors((i>>1));
		ret=max(ret,seg[i]);
		return ret;
	}
}seg1,seg2;
int now=1;

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){
	now++;
	int fl1=(int)seg1.v.size(),fl2=(int)seg2.v.size();
	if(para==0){
		seg1.upd(1,0,kaf-1,1,m+5,make_pair(now,-2));
		seg2.upd(1,0,kaf-1,1,m+5,make_pair(now,-2));
	}
	else{
		for(int i=0;i<(int)alled[par[u]].w.size();i++){
			alled[par[u]].dp[i].first=seg1.pors(kaf+alled[par[u]].w[i].first).second;
			alled[par[u]].dp[i].second=seg2.pors(kaf+alled[par[u]].w[i].second).second;
			if(alled[par[u]].dp[i].first==-2){
				alled[par[u]].dp[i].first=alled[par[u]].w[i].first;
			}
			if(alled[par[u]].dp[i].second==-2){
				alled[par[u]].dp[i].second=alled[par[u]].w[i].second;
			}
		}
		if((int)alled[par[u]].w.size()>0){
			seg1.upd(1,0,kaf-1,1,alled[par[u]].w[0].first-1,make_pair(now,alled[par[u]].dp[0].first));
			seg2.upd(1,0,kaf-1,alled[par[u]].w.back().second+1,m+5,make_pair(now,alled[par[u]].dp.back().second));
			seg2.upd(1,0,kaf-1,1,alled[par[u]].w[0].first-1,make_pair(now,-1));
			seg1.upd(1,0,kaf-1,alled[par[u]].w.back().second+1,m+5,make_pair(now,m+10));
			for(int i=1;i<(int)alled[par[u]].w.size();i++){
				seg1.upd(1,0,kaf-1,alled[par[u]].w[i-1].second+1,alled[par[u]].w[i].first-1,make_pair(now,alled[par[u]].dp[i].first));
				seg2.upd(1,0,kaf-1,alled[par[u]].w[i-1].second+1,alled[par[u]].w[i].first-1,make_pair(now,alled[par[u]].dp[i-1].second));
			}
		}
		else{
			seg1.upd(1,0,kaf-1,1,m+5,make_pair(now,m+10));
			seg2.upd(1,0,kaf-1,1,m+5,make_pair(now,-1));
		}
	}
	for(auto xx:adj[u]){
		int x=alled[xx].getad(u);
		if(vis[x]==0&&x!=para){
			calalllink(x,u);
		}
	}
	seg1.back(fl1);
	seg2.back(fl2);
}

void solve(int u){
	dfs(u);
	fake.clear();
	fn=sz[u];
	int v=finds(u);
	fake.clear();
	dfs(v);
	now=1;	
	calalllink(v);
	for(auto x:fake){
		if(x==v){
			khod[v].push_back(0);
			continue;
		}
		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 11 ms 21076 KB Output is correct
2 Correct 10 ms 21076 KB Output is correct
3 Correct 10 ms 21060 KB Output is correct
4 Correct 11 ms 21088 KB Output is correct
5 Correct 12 ms 21080 KB Output is correct
6 Correct 19 ms 21204 KB Output is correct
7 Correct 143 ms 23116 KB Output is correct
8 Correct 133 ms 23140 KB Output is correct
9 Correct 140 ms 23144 KB Output is correct
10 Correct 2281 ms 42456 KB Output is correct
11 Correct 2367 ms 42480 KB Output is correct
12 Correct 3425 ms 91552 KB Output is correct
13 Correct 396 ms 41496 KB Output is correct
14 Correct 1841 ms 47692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1308 ms 70296 KB Output is correct
2 Correct 1227 ms 68584 KB Output is correct
3 Correct 2083 ms 94200 KB Output is correct
4 Correct 1943 ms 91800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21004 KB Output is correct
2 Correct 12 ms 21064 KB Output is correct
3 Correct 11 ms 21136 KB Output is correct
4 Correct 11 ms 21148 KB Output is correct
5 Correct 11 ms 21064 KB Output is correct
6 Correct 26 ms 21728 KB Output is correct
7 Correct 217 ms 28412 KB Output is correct
8 Correct 3353 ms 92540 KB Output is correct
9 Correct 3387 ms 92520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3322 ms 92336 KB Output is correct
2 Correct 2064 ms 94900 KB Output is correct
3 Correct 2111 ms 95340 KB Output is correct
4 Correct 2061 ms 93824 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21076 KB Output is correct
2 Correct 13 ms 21076 KB Output is correct
3 Correct 10 ms 21048 KB Output is correct
4 Correct 12 ms 21076 KB Output is correct
5 Correct 18 ms 21288 KB Output is correct
6 Correct 135 ms 23280 KB Output is correct
7 Correct 2302 ms 43224 KB Output is correct
8 Correct 3209 ms 92448 KB Output is correct
9 Correct 407 ms 42804 KB Output is correct
10 Correct 1758 ms 48968 KB Output is correct
11 Correct 1247 ms 71496 KB Output is correct
12 Correct 1251 ms 71576 KB Output is correct
13 Correct 2064 ms 95516 KB Output is correct