Cod sursa(job #548869)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 7 martie 2011 21:15:10
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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],arb2[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 ;
	arb2[nod].insert(a2);
	if (a<=st && dr<=b)
	{
		arb[nod].insert(a2);
		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() && (*it)<=b2)
		found=1;
	if (a<=st && dr<=b)
	{
		it=arb2[nod].lower_bound(a2);
		if (it!=arb2[nod].end() && (*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;
}