Cod sursa(job #542331)

Utilizator Catah15Catalin Haidau Catah15 Data 26 februarie 2011 11:50:40
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

#define MAXN 100005

int depend[MAXN];
int n, m, q;
bool contor[MAXN];
int conex = 1;
deque <int> deq[MAXN];
vector <int> lista[MAXN];
int tata[MAXN];
vector <int> goss[MAXN];


ifstream f("gossips.in");
ofstream g("gossips.out");


void vecini (int nod)
{
	contor[nod] = 1;
	
	deq[conex].push_back(nod);
	depend[nod] = conex;
	
	for (unsigned int i = 0; i < lista[nod].size(); ++i)
		if ( ! contor[lista[nod][i]] )
			vecini(lista[nod][i]);
	
}


int father(int x, int y)
{
	if (! tata[y])
		return 0;
	
	goss[depend[x]].push_back(tata[y]);
	
	father(x, tata[y]);

}


int main()
{
	
	f >> n >> m >> q;
	
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		
		f >> a >> b;
		
		lista[a].push_back(b);
		lista[b].push_back(a);
		
		tata[b] = a;
	}
	
	for (int i = 1; i <= n; ++i)
	{
		if (contor[i])
			continue;
		
		contor[i] = 1;
		
		deq[conex].push_back(i);
		depend[i] = conex;
		
		for (unsigned int j = 0; j < lista[i].size(); ++j)
			if ( ! contor[lista[i][j]] )
				vecini(lista[i][j]);
		
		++conex;
	}
	
	for (int i = 1; i <= q; ++i)
	{
		int type, x, y;
		
		f >> type >> x >> y;
		
		if (type == 2)
		{	
			goss[depend[x]].push_back(y);
			
			father(x, y);
		}
		
		if (type == 1)
		{
			for (unsigned int j = 0; j < goss[depend[x]].size(); ++j)
				if (goss[depend[x]][j] == y)
				{
					g << "YES\n";
					goto FIN;
				}
			g << "NO\n";
			
			FIN: ;
			
		}
		
	}
	
	
}