Cod sursa(job #542510)

Utilizator Teodor94Teodor Plop Teodor94 Data 26 februarie 2011 14:25:54
Problema Pixels Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.11 kb
#include<cstdio>
#include<vector>

using namespace std;

const int N=100005;
const int K=4000;

vector <int> next[N];
int n,m,q,pred[N],v[N],nrv,nr[N];
bool a[K][K];

void citire()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	int a,b;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		pred[b]=a;
		next[a].push_back(b);
		++nr[a];
	}
}

void dfs(int x)
{
	for (int i=1;i<=nrv;++i)
		a[x][v[i]]=true;
	for (int i=0;i<nr[x];++i)
		dfs(next[x][i]);
}

void barfa(int x,int y)
{
	int cur=y;
	nrv=1;
	v[nrv]=cur;
	while (pred[cur]!=0)
	{
		++nrv;
		v[nrv]=pred[cur];
		cur=pred[cur];
	}
	cur=x;
	while (cur!=0)
	{
		for (int i=1;i<=nrv;++i)
			a[cur][v[i]]=true;
		cur=pred[cur];
	}
	for (int i=0;i<nr[x];++i)
		dfs(next[x][i]);
}


void intreb(int x,int y)
{
	if (a[x][y])
		printf("YES\n");
	else
		printf("NO\n");
}

void rez()
{
	int aa,x,y;
	for (int i=1;i<=q;++i)
	{
		scanf("%d%d%d",&aa,&x,&y);
		if (aa==2)
			barfa(x,y);
		else
			intreb(x,y);
	}
}

int main()
{
	citire();
	rez();
	return 0;
}