Submission #1667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1667		ainta	Synchronization (JOI13_synchronization)	C++98	100 / 100	4494 ms	16032 KiB

synchronization

#include<stdio.h>
#include<algorithm>
using namespace std;
int N,M,QQ,P[200001],c,S[100001],Count[200001],T[1001],E2[200001][2],Q[200001];
int s[200001],l[200001],num[200001],End[200001],Save[100001],ord[200001];

struct stack{
	int a,b;
}st[200001];

struct Edge{
	int x,y,z;
	bool operator <(const Edge &p)const{
		return x!=p.x?x<p.x:y<p.y;
	}
}E[400001];

bool connect[100001],v[200001];

void DFS()
{
	int i,top=0,C=0;
	st[++top].a=1,st[top].b=s[1],num[1]=++C;
	v[1]=true;
	while(1){
		while(top){
			while(st[top].b!=l[st[top].a]&&v[E[st[top].b].y])st[top].b++;
			if(st[top].b!=l[st[top].a])break;
			End[st[top].a]=C;
			top--;
		}
		if(!top)break;
		st[top+1].a=E[st[top].b++].y;
		top++;
		st[top].b=s[st[top].a];
		num[st[top].a]=++C;
		v[st[top].a]=true;
	}
	for(i=1;i<=N;i++)ord[num[i]]=i;
}

void BFS(int a)
{
	int h=0,t=0,i,x;
	Q[++t]=a,P[a]=a;
	while(h<t)
	{
		x=Q[++h];
		for(i=s[x];i<l[x];i++){
			if(!P[E[i].y] && connect[E[i].z]){
				Q[++t]=E[i].y;
				P[E[i].y]=a;
				Count[Q[t]]=Count[a];
			}
		}
	}
}

void Do()
{
	int i,j,cc=0,a,b;
	for(i=0;i<c;i++){
		T[cc++]=E2[S[i]][0];
		T[cc++]=E2[S[i]][1];
	}
	for(i=0;i<c;i++){
		a=T[i*2],b=T[i*2+1];
		if(num[b]<num[a])swap(a,b);
		connect[S[i]]=!connect[S[i]];
		if(connect[S[i]])
		{
			Count[P[a]]=Count[P[a]]+Count[b]-Save[S[i]];
			for(j=0;j<cc;j++){
				if(P[T[j]]==P[a]||P[T[j]]==b)Count[T[j]]=Count[P[a]],P[T[j]]=P[a];
			}
		}
		else
		{
			for(j=0;j<cc;j++){
				if(P[T[j]]==P[a] && num[T[j]]>=num[b] && num[T[j]]<=End[b])P[T[j]]=b;
			}
			Save[S[i]]=Count[b];
		}
	}
	for(i=1;i<=N;i++)P[i]=0;
	for(i=1;i<=N;i++){
		if(!P[ord[i]])BFS(ord[i]);
	}
}

void init()
{
	int i,t;
	for(i=1;i<=N;i++)P[i]=i,Count[i]=1;
	t=E[0].x;
	for(i=1;i<c;i++){
		if(E[i].x!=t){
			s[E[i].x]=l[t]=i;
			t=E[i].x;
		}
	}
	l[t]=i;
	DFS();
}

int main()
{
	scanf("%d%d%d",&N,&M,&QQ);
	int i;
	c=0;
	for(i=1;i<N;i++)
	{
		scanf("%d%d",&E[c].x,&E[c].y);
		E2[i][0]=E[c].x,E2[i][1]=E[c].y;
		E[c++].z=i;
		E[c].x=E[c-1].y,E[c].y=E[c-1].x,E[c++].z=i;
	}
	sort(E,E+c);
	init();
	c=0;
	while(M--){
		scanf("%d",&S[c++]);
		if(c==500){
			Do();
			c=0;
		}
	}
	Do();
	while(QQ--){
		scanf("%d",&i);
		printf("%d\n",Count[P[i]]);
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40