Cod sursa(job #542389)

Utilizator Catah15Catalin Haidau Catah15 Data 26 februarie 2011 12:53:13
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.07 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 get_father (int nod, int y)
{
	if (! tata[nod])
		return 0;
	
	goss[tata[nod]].push_back(y);
	
	get_father (tata[nod], y);
	
	return 0 ;
}*/


void get_son (int nod, int y)
{
	goss[nod].push_back(y);
	
	for (unsigned int i = 0; i < lista[nod].size(); ++i)
		if (lista[nod][i] != tata[nod])
			get_son (lista[nod][i], y);
}


int search (int x, int nod)
{
	for (unsigned int i = 0; i < goss[x].size(); ++i)
		if (goss[x][i] == nod)
			return 1;
	return 0;
}



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(depend[x] == depend[y] && type == 1)
		{
			g << "NO\n";
			continue;
		}
		
		if (type == 2)
		{	
			while (y != 0)
			{
				goss[x].push_back(y);
				
				//get_father(x, y);
				
				for (unsigned int j = 0; j < lista[x].size(); ++j)
					//if (lista[x][j] != tata[x])
						get_son(lista[x][j], y);
					
				y = tata[y];
			}
		}
		
		if (type == 1)
		{
			if (search(x, y))
				g << "YES\n";
			else
				g <<"NO\n";
		}
	}
	
	return 0;
	
}