Cod sursa(job #542458)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 26 februarie 2011 13:49:43
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.74 kb
#include <fstream>
using namespace std;
ifstream fin("gossips.in");
ofstream fout("gossips.out");

#include <vector>
#include <queue>
#define maxn 100005
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

int i,N,M,q,c,x,y,R;
vector <pair<int,int> > A[maxn];
vector <int> B[maxn];
queue<int> Q;
bool v[maxn];
int G[maxn];

void citire()
{
	fin >> N >> M >> q;
	for(i=1;i<=M;i++)
	{
		fin >> x >> y;
		A[x].pb(mp(y,1));
		A[y].pb(mp(x,0));
	}
}

int verific(int x, int y)
{
	vector<int> :: iterator it;
	for(it=B[x].begin();it!=B[x].end();it++)
		if(*it==y) return 1;
	return 0;
}

void barfa()
{
	int k;
	vector <pair<int,int> > :: iterator it;
	for(i=1;i<=G[0];i++) G[i]=0;
	G[0]=0;
	Q.push(x);
	G[++G[0]]=x;
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(it=A[k].begin();it!=A[k].end();it++)
			if(!v[it->ff] && it->ss==0)
			{
				int nod=it->ff;
				v[it->ff]=1;
				Q.push(it->ff);
				G[++G[0]]=it->ff;
			}
	}
	for(i=1;i<=N;i++) v[i]=0;
	Q.push(x);
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(it=A[k].begin();it!=A[k].end();it++)
			if(!v[it->ff] && it->ss==1)
			{
				v[it->ff]=1;
				Q.push(it->ff);
				G[++G[0]]=it->ff;
			}
	}
	for(i=1;i<=N;i++) v[i]=0;
	Q.push(y);
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(i=1;i<=G[0];i++) B[G[i]].pb(k);
		for(it=A[k].begin();it!=A[k].end();it++)
			if(!v[it->ff] && it->ss==0)
			{
				v[it->ff]=1;
				Q.push(it->ff);
			}
	}
}

int main()
{
	citire();
	for(;q;q--)
	{
		fin >> c >> x >> y;
		for(i=1;i<=N;i++) v[i]=0;
		while(!Q.empty()) Q.pop();
		if(c==1)
		{
			R=verific(x,y);
			if(R) fout << "YES";
			else fout << "NO";
			fout << '\n';
		}
		if(c==2)
			barfa();
	}
}