Cod sursa(job #542313)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 26 februarie 2011 11:20:34
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 0.86 kb
#include <cstdio>
#include <bitset>

#define maxN 100005

using namespace std;

int N, M, Q, c[maxN], t[maxN], nrcomp;
bitset <maxN> mybit[maxN/100];

void DF (int node)
{
	if (!t[node]) {
		if (c[node] == 0)
			c[node] = nrcomp++;
		return ;
	}
	else {
		DF (t[node]);
		c[node] = c[t[node]];
	}
}

int main ()
{


	freopen ("gossips.in", "r", stdin);
	freopen ("gossips.out", "w", stdout);


	scanf ("%d %d %d\n", &N, &M, &Q);
	
	int x, y, Y, i, op;
	while (M--)
	{
		scanf ("%d %d\n", &x, &y);
		t[y] = x;
	}
	for (i = 1; i <= N; i++) 
		if (!c[i])
			DF (i);
	while (Q--)
	{
		scanf ("%d %d %d\n", &op, &x, &y);
		if (op == 2) //insert
		{
			Y = y;
			
			while (Y != 0) {
				if (mybit[c[x]][Y] == 0)
					mybit[c[x]][Y] = 1;
				Y = t[Y];
			}
		}
		else {
			if (mybit[c[x]][y] == 1 || c[x] == c[y])
				printf ("YES\n");
			else printf ("NO\n");
		}
	}
	return 0;
}