Cod sursa(job #542463)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 26 februarie 2011 13:57:07
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 0.95 kb
#include <cstdio>
#include <cstring>

#define file_in "gossips.in"
#define file_out "gossips.out"

#define nmax 101100

int n,m,q;
int a,b,i,tip,dd;
int d[nmax];
int x[nmax];
int y[nmax];

int bf(int nod, int nodd){
	
	for (i=1;i<=m;++i)
	{
		if (y[i]==nod)
			d[x[i]]=1;
	}
	
	for (i=1;i<=n;++i)
		if (i!=nod)
		 if (d[i]==0)
			 d[i]=0x3f3f3f3f;
		 
	int ok=1;

    while(ok)
    {
		ok=0;
		for (i=1;i<=m;++i)
			 if (d[y[i]]>d[x[i]]+1)
				 d[y[i]]=d[x[i]]+1,
				 ok=1;
	}
	
	 if (d[nodd]==0x3f3f3f3f)
			 return 0;
		return 1;
}



int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n, &m, &q);
	
	for (i=1;i<=m;++i)
		 scanf("%d %d", &y[i], &x[i]);
	while(q--){
		
		scanf("%d %d %d", &tip, &a, &b);
		if (tip==2){
			x[++m]=a;
			y[m]=b;
		}
		else{
			dd=bf(a,b);
			if (dd)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	
	return 0;
	
}