Submission #1314129

#TimeUsernameProblemLanguageResultExecution timeMemory
1314129boclobanchatSynchronization (JOI13_synchronization)C++20
100 / 100
5876 ms113116 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int N=6767;
bitset<N> bt[MAXN];
vector<int> vi[MAXN*8];
pair<int,int> edge[MAXN];
int pos[MAXN],ans[MAXN],dsu[MAXN],cnt[MAXN];
stack< pair<int,int> > st;
int root(int i)
{
	if(!dsu[i]) return i;
	return root(dsu[i]);
}
void merge(int i,int j,int p)
{
	i=root(i),j=root(j);
	if(cnt[i]<cnt[j]) swap(i,j);
	dsu[j]=i,cnt[i]+=cnt[j],bt[i]|=bt[j];
	st.push({i,j});
}
void rollback()
{
	int l=st.top().first,r=st.top().second;
	st.pop();
	dsu[r]=0,cnt[l]-=cnt[r],bt[r]=bt[l];
}
void update(int l,int r,int u,int v,int val,int pos)
{
	if(v<l||r<u) return ;
	if(u<=l&&r<=v)
	{
		vi[pos].push_back(val);
		return ;
	}
	int mid=(l+r)/2;
	update(l,mid,u,v,val,pos*2);
	update(mid+1,r,u,v,val,pos*2+1);
}
void dnc(int l,int r,int pos)
{
	for(auto v:vi[pos]) merge(edge[v].first,edge[v].second,v);
	if(l!=r)
	{
		int mid=(l+r)/2;
		dnc(l,mid,pos*2);
		dnc(mid+1,r,pos*2+1);
	}
	for(auto v:vi[pos]) rollback();
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<n;i++) cin>>edge[i].first>>edge[i].second;
	for(int i=1;i<=m;i++)
	{
		int res;
		cin>>res;
		if(!pos[res]) pos[res]=i;
		else
		{
			update(1,m,pos[res],i-1,res,1);
			pos[res]=0;
		}
	}
	for(int i=1;i<n;i++) if(pos[i]) update(1,m,pos[i],m,i,1);
	int pre=1;
	for(int i=1;i<=n;i++) cnt[i]=1;
	for(int i=1;i<=n;i++) if(i%N==0||i==n)
	{
		for(int j=pre;j<=i;j++) bt[j][(j-1)%N]=1;
		pre=i+1;
		dnc(1,m,1);
		for(int j=1;j<=n;j++) ans[j]+=bt[j].count(),bt[j]=0;
	}
	while(q--)
	{
		int res;
		cin>>res;
		cout<<ans[res]<<"\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...