oj.uz

Submission #753755

# Submission time Handle Problem Language Result Execution time Memory
753755 2023-06-05T22:39:59 Z amirhoseinfar1385 Synchronization (JOI13_synchronization) C++17
100 / 100
 1653 ms 86960 KB 
#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;
	}
};
char c;  
void fastscan(int &nu)
{
    nu = 0;
    c = getchar();
    for (; (c>47 && c<58); c=getchar())
        nu = nu *10 + c - 48;
}
yal alled[maxn];
vector<int>adj[maxn],cnt[maxn*2],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)];
	pair<int,int>v[maxn*20];
	int z;
	segment(){
		z=0;
	}
	void back(int len){
		while(z>len){
			seg[v[z].first]=v[z].second;
			z--;
		}
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			z++;
			v[z].first=i;
			v[z].second=seg[i];
			seg[i]=w;
			return ;
		}
		int m=(l+r)>>1;
		if(!(l>tr||m<tl))
			upd((i<<1),l,m,tl,tr,w);
		if(!(m>=tr||r<tl))
			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.z;
	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);
		}
		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);
		cnt[ff].push_back(azb[x]);
	}
	sort(khod[v].begin(),khod[v].end());
	for(auto x:khod[v]){
		if(x==0){
			continue;
		}
		bal[cnt[x].back()].push_back(x);
		cnt[x].pop_back();
	}
	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);
	fastscan(n);
	fastscan(m);
	fastscan(q);
	for(int i=1;i<=n-1;i++){
		fastscan(alled[i].u);fastscan(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;
		fastscan(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);
	vector<int>mainres;
	for(int i=0;i<q;i++){
		int u;
		fastscan(u);
		mainres.push_back(res[u]);
	}
	for(auto x:mainres){
		cout<<x<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35540 KB Output is correct
2 Correct 18 ms 35496 KB Output is correct
3 Correct 17 ms 35544 KB Output is correct
4 Correct 18 ms 35548 KB Output is correct
5 Correct 18 ms 35624 KB Output is correct
6 Correct 23 ms 35832 KB Output is correct
7 Correct 92 ms 38332 KB Output is correct
8 Correct 90 ms 38336 KB Output is correct
9 Correct 94 ms 38580 KB Output is correct
10 Correct 1422 ms 62468 KB Output is correct
11 Correct 1307 ms 62436 KB Output is correct
12 Correct 1523 ms 69080 KB Output is correct
13 Correct 269 ms 61856 KB Output is correct
14 Correct 1168 ms 68928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 76772 KB Output is correct
2 Correct 594 ms 76388 KB Output is correct
3 Correct 1027 ms 85320 KB Output is correct
4 Correct 948 ms 85304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 18 ms 35544 KB Output is correct
3 Correct 18 ms 35540 KB Output is correct
4 Correct 18 ms 35572 KB Output is correct
5 Correct 19 ms 35560 KB Output is correct
6 Correct 25 ms 35916 KB Output is correct
7 Correct 128 ms 39252 KB Output is correct
8 Correct 1565 ms 70228 KB Output is correct
9 Correct 1559 ms 70332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 70080 KB Output is correct
2 Correct 1020 ms 86604 KB Output is correct
3 Correct 1081 ms 86920 KB Output is correct
4 Correct 1025 ms 86812 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35608 KB Output is correct
2 Correct 18 ms 35540 KB Output is correct
3 Correct 19 ms 35504 KB Output is correct
4 Correct 18 ms 35648 KB Output is correct
5 Correct 22 ms 35796 KB Output is correct
6 Correct 93 ms 38732 KB Output is correct
7 Correct 1444 ms 63572 KB Output is correct
8 Correct 1653 ms 70472 KB Output is correct
9 Correct 253 ms 62824 KB Output is correct
10 Correct 1245 ms 70008 KB Output is correct
11 Correct 639 ms 78268 KB Output is correct
12 Correct 657 ms 78232 KB Output is correct
13 Correct 1048 ms 86960 KB Output is correct