oj.uz

답안 #753736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753736 2023-06-05T19:39:22 Z amirhoseinfar1385 동기화 (JOI13_synchronization) C++17
100 / 100
 1818 ms 68996 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],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);
	fastscan(n);
	fastscan(m);
	fastscan(q);
//	cin>>n>>m>>q;
	for(int i=1;i<=n-1;i++){
		fastscan(alled[i].u);fastscan(alled[i].v);
		//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;
		fastscan(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;
		fastscan(u);
		cout<<res[u]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 7 ms 15256 KB Output is correct
3 Correct 8 ms 15224 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 7 ms 15188 KB Output is correct
6 Correct 13 ms 15444 KB Output is correct
7 Correct 87 ms 17512 KB Output is correct
8 Correct 86 ms 17484 KB Output is correct
9 Correct 100 ms 17612 KB Output is correct
10 Correct 1355 ms 38652 KB Output is correct
11 Correct 1480 ms 38572 KB Output is correct
12 Correct 1672 ms 58588 KB Output is correct
13 Correct 225 ms 38212 KB Output is correct
14 Correct 1125 ms 44200 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 56312 KB Output is correct
2 Correct 680 ms 55496 KB Output is correct
3 Correct 1124 ms 68264 KB Output is correct
4 Correct 1096 ms 67612 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 10 ms 15188 KB Output is correct
4 Correct 8 ms 15228 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 17 ms 15704 KB Output is correct
7 Correct 133 ms 19604 KB Output is correct
8 Correct 1818 ms 58800 KB Output is correct
9 Correct 1690 ms 58784 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1732 ms 58948 KB Output is correct
2 Correct 1158 ms 68792 KB Output is correct
3 Correct 1145 ms 68924 KB Output is correct
4 Correct 1135 ms 68976 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 7 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 13 ms 15444 KB Output is correct
6 Correct 86 ms 17544 KB Output is correct
7 Correct 1419 ms 38732 KB Output is correct
8 Correct 1690 ms 58868 KB Output is correct
9 Correct 237 ms 38808 KB Output is correct
10 Correct 1146 ms 44852 KB Output is correct
11 Correct 716 ms 56920 KB Output is correct
12 Correct 717 ms 56876 KB Output is correct
13 Correct 1187 ms 68996 KB Output is correct