Cod sursa(job #548056)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 martie 2011 23:57:20
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#include <vector>
#include <set>
#define NMAX 100005
#define LMAX (1<<18)
#define pb push_back
using namespace std;
int n,m,q,dad[NMAX],inc[NMAX],sf[NMAX],r,init[NMAX];
int a,b,a2,b2,found;
vector <int> A[NMAX];
set <int> arb[LMAX];
set <int> :: iterator it;
void read()
{
	scanf("%d%d%d",&n,&m,&q);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		A[x].pb(y); dad[y]=x;
	}
	for (i=1; i<=n; i++)
		if (!dad[i])
			A[0].pb(i);
}
void dfs(int nod)
{
	if (nod)
		inc[nod]=++r;
	int i,vec;
	for (i=0; i<A[nod].size(); i++)
	{
		vec=A[nod][i];
		dfs(vec);
	}
	sf[nod]=r;
}
void update(int st,int dr,int nod)
{
	if (dr<a || b<st)
		return ;
	arb[nod].insert(a2);
	if (a<=st && dr<=b)
		return ;
	int mij=(st+dr)/2;
	update(st,mij,nod*2);
	update(mij+1,dr,nod*2+1);
}
void search(int st,int dr,int nod)
{
	if (found)
		return ;
	if (dr<a || b<st)
		return ;
	it=arb[nod].lower_bound(a2);
	if (it!=arb[nod].end())
		if ((*it)>=a2 && (*it)<=b2)
		{
			found=1;
			return ;
		}
	if (a<=st && dr<=b)
	{
		it=arb[nod].lower_bound(a2);
		if (it!=arb[nod].end())
			if ((*it)>=a2 && (*it)<=b2)
				found=1;
		return ;
	}
	int mij=(st+dr)/2;
	search(st,mij,nod*2);
	search(mij+1,dr,nod*2+1);
}
void solve()
{
	int i,tip,x,y;
	for (i=1; i<=q; i++)
	{
		scanf("%d%d%d",&tip,&x,&y);
		if (tip==2)
		{
			a=inc[x]; b=sf[x]; a2=inc[y];
			update(1,n,1);
		}
		if (tip==1)
		{
			a=inc[x]; b=sf[x];
			a2=inc[y]; b2=sf[y];
			found=0;
			search(1,n,1);
			if (found)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
}
int main()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	read();
	dfs(0);
	solve();
	return 0;
}