Cod sursa(job #542362)

Utilizator skullLepadat Mihai-Alexandru skull Data 26 februarie 2011 12:27:22
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.2 kb
#include <stdio.h>
#include <vector>
#include <set>
#include <queue>
using namespace std;
#define nmax 100005

vector<int> stie, F[nmax];
int tata[nmax];
set<int> G[nmax];
int N, M, Q;

void citire ()
{
	int i, x, y;
	scanf("%d%d%d", &N, &M, &Q);
	for (i = 1; i <= M; ++i)
	{
		scanf("%d%d", &x, &y);
		tata[y] = x;
		F[x].push_back(y);
	}
}

void dfs(int x, int y)
{
	int i;
	for (i = 0; i < stie.size(); ++i) G[x].insert(stie[i]);
	for (i = 0; i < F[x].size(); ++i) dfs(F[x][i], y);
}

void solve ()
{
	int tip, x, y, i, nod;
	while (Q--)
	{
		scanf("%d%d%d", &tip, &x, &y);
		if (tip == 2)
		{
			nod = y;
			while (tata[nod])
			{
				stie.push_back(nod);
				nod = tata[nod];
			}
			stie.push_back(nod);
			
			dfs(x, y);
			
			nod = x;
			while ( tata[nod] )
			{
				for (i = 0; i < stie.size(); ++i) G[nod].insert(stie[i]);
				nod = tata[nod];
			}
			for (i = 0; i < stie.size(); ++i) G[nod].insert(stie[i]);
			
			stie.clear();
		}
		else
			if (G[x].find(y) != G[x].end() ) printf("YES\n");
				else printf("NO\n");
	}
}

int main ()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	citire ();
	solve ();
	return 0;
}