oj.uz

Submission #1667

# Submission time Handle Problem Language Result Execution time Memory
1667 2013-07-11T20:39:23 Z ainta Synchronization (JOI13_synchronization) C++
100 / 100
 4494 ms 16032 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16032 KB Output is correct
2 Correct 0 ms 16032 KB Output is correct
3 Correct 0 ms 16032 KB Output is correct
4 Correct 0 ms 16032 KB Output is correct
5 Correct 0 ms 16032 KB Output is correct
6 Correct 3 ms 16032 KB Output is correct
7 Correct 63 ms 16032 KB Output is correct
8 Correct 62 ms 16032 KB Output is correct
9 Correct 64 ms 16032 KB Output is correct
10 Correct 4494 ms 16032 KB Output is correct
11 Correct 4492 ms 16032 KB Output is correct
12 Correct 1324 ms 16032 KB Output is correct
13 Correct 2170 ms 16032 KB Output is correct
14 Correct 2254 ms 16032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 16032 KB Output is correct
2 Correct 1074 ms 16032 KB Output is correct
3 Correct 606 ms 16032 KB Output is correct
4 Correct 586 ms 16032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16032 KB Output is correct
2 Correct 0 ms 16032 KB Output is correct
3 Correct 0 ms 16032 KB Output is correct
4 Correct 0 ms 16032 KB Output is correct
5 Correct 0 ms 16032 KB Output is correct
6 Correct 2 ms 16032 KB Output is correct
7 Correct 45 ms 16032 KB Output is correct
8 Correct 1324 ms 16032 KB Output is correct
9 Correct 1391 ms 16032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 16032 KB Output is correct
2 Correct 605 ms 16032 KB Output is correct
3 Correct 639 ms 16032 KB Output is correct
4 Correct 635 ms 16032 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16032 KB Output is correct
2 Correct 0 ms 16032 KB Output is correct
3 Correct 0 ms 16032 KB Output is correct
4 Correct 0 ms 16032 KB Output is correct
5 Correct 4 ms 16032 KB Output is correct
6 Correct 71 ms 16032 KB Output is correct
7 Correct 3986 ms 16032 KB Output is correct
8 Correct 1129 ms 16032 KB Output is correct
9 Correct 1898 ms 16032 KB Output is correct
10 Correct 1821 ms 16032 KB Output is correct
11 Correct 923 ms 16032 KB Output is correct
12 Correct 924 ms 16032 KB Output is correct
13 Correct 521 ms 16032 KB Output is correct