Cod sursa(job #542348)

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

vector<int> Gs[nmax], Gf[nmax], stie;
set<int> G[nmax];
int N, M, Q;
queue<int> Coada;

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

void solve ()
{
	int tip, x, y, i, nod;
	while (Q--)
	{
		scanf("%d%d%d", &tip, &x, &y);
		if (tip == 2)
		{
			Coada.push(y);
			while (!Coada.empty())
			{
				nod = Coada.front(); Coada.pop();
				stie.push_back(nod);
				for (i = 0; i < Gf[nod].size(); ++i)
					Coada.push(Gf[nod][i]);
			}
			Coada.push(x);
			while (!Coada.empty())
			{
				nod = Coada.front(); Coada.pop ();
				for (i = 0; i < stie.size(); ++i) G[nod].insert(stie[i]);
				for (i = 0; i < Gs[nod].size(); ++i)
					Coada.push(Gs[nod][i]);
			}
			Coada.push(x);
			while (!Coada.empty())
			{
				nod = Coada.front(); Coada.pop();
				for (i = 0; i < stie.size(); ++i) G[nod].insert(stie[i]);
				for (i = 0; i < Gf[nod].size(); ++i)
					Coada.push(Gf[nod][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;
}