Cod sursa(job #542426)

Utilizator CiurelVictorCiurel Victor CiurelVictor Data 26 februarie 2011 13:18:03
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.05 kb
#include<stdio.h>

int n,m,q,a[2500][2500],x,y,caz,d[2500][2500],c[2500],v[2500],kk;

void adauga();
void bfs(int,int,int,int);

int main()
{
	int i;
	
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	
	scanf("%d %d %d",&n,&m,&q);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		a[x][y]=-1;
		a[y][x]=1;
	}
	
	for(;q;q--)
	{
		scanf("%d %d %d",&caz,&x,&y);
		
		if(caz==2)
			adauga();
		else
		{
			if(d[x][y])
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	
	
}

void adauga()
{
	int i,j;
	
	for(i=1;i<=n;i++)
		v[i]=0;
	
	c[0]=y;
	v[y]=1;
	
	bfs(0,0,1,2);
	
	for(i=0;i<=kk;i++)
		d[x][c[i]]=1;
	
	for(i=1;i<=n;i++)
		v[i]=0;
	
	c[0]=x;
	v[x]=1;
	
	bfs(0,0,1,-1);
	
	for(i=1;i<=kk;i++)
		for(j=1;j<=n;j++)
			d[c[i]][j]=d[x][j];		
}

void bfs(int ii,int jj,int o,int p)
{
	int i;
	
	if(ii<=jj)
	{
		for(i=1;i<=n;i++)
			if((a[c[ii]][i]==o||a[c[ii]][i]==p)&&v[i]==0)
			{
				v[i]=1;
				jj++;
				c[jj]=i;
			}
			
		kk=jj;
		
		bfs(ii+1,jj,o,p);
	}
}