oj.uz

답안 #753753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753753 2023-06-05T22:17:12 Z amirhoseinfar1385 동기화 (JOI13_synchronization) C++17
100 / 100
 1696 ms 96600 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*30];
	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(l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			z++;
			v[z]=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.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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 43348 KB Output is correct
2 Correct 20 ms 43428 KB Output is correct
3 Correct 20 ms 43328 KB Output is correct
4 Correct 20 ms 43424 KB Output is correct
5 Correct 21 ms 43472 KB Output is correct
6 Correct 25 ms 43672 KB Output is correct
7 Correct 100 ms 46156 KB Output is correct
8 Correct 93 ms 46296 KB Output is correct
9 Correct 92 ms 46260 KB Output is correct
10 Correct 1328 ms 72368 KB Output is correct
11 Correct 1450 ms 72144 KB Output is correct
12 Correct 1543 ms 78616 KB Output is correct
13 Correct 251 ms 70948 KB Output is correct
14 Correct 1260 ms 77940 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 621 ms 86100 KB Output is correct
2 Correct 611 ms 85776 KB Output is correct
3 Correct 995 ms 94516 KB Output is correct
4 Correct 967 ms 94424 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 19 ms 43396 KB Output is correct
3 Correct 19 ms 43400 KB Output is correct
4 Correct 22 ms 43372 KB Output is correct
5 Correct 22 ms 43388 KB Output is correct
6 Correct 27 ms 43808 KB Output is correct
7 Correct 129 ms 47052 KB Output is correct
8 Correct 1696 ms 80324 KB Output is correct
9 Correct 1552 ms 80312 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1646 ms 80340 KB Output is correct
2 Correct 1053 ms 96252 KB Output is correct
3 Correct 1038 ms 96600 KB Output is correct
4 Correct 1030 ms 96576 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 43348 KB Output is correct
2 Correct 21 ms 43384 KB Output is correct
3 Correct 20 ms 43400 KB Output is correct
4 Correct 20 ms 43416 KB Output is correct
5 Correct 25 ms 43648 KB Output is correct
6 Correct 95 ms 46388 KB Output is correct
7 Correct 1459 ms 73688 KB Output is correct
8 Correct 1589 ms 80564 KB Output is correct
9 Correct 269 ms 72592 KB Output is correct
10 Correct 1208 ms 79588 KB Output is correct
11 Correct 628 ms 88144 KB Output is correct
12 Correct 637 ms 88132 KB Output is correct
13 Correct 1012 ms 96536 KB Output is correct