Cod sursa(job #552201)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 11 martie 2011 20:26:13
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define nmax 100010

int n, m, q, a[nmax], b[nmax], h, val, st, dr, a1, b1, ok;
set <int> arb[4*nmax], arb2[4*nmax];
vector <int> g[nmax];
char u[nmax];

void df(int nod)
{
	int i;
	a[nod]=++h;
	for (i=0; i<g[nod].size(); i++) 
		if (!a[g[nod][i]]) df(g[nod][i]);
	b[nod]=h;
}

void update(int nod, int l, int r)
{
	arb2[nod].insert(val);
	if (st<=l && r<=dr) arb[nod].insert(val); else
	{
		int m=(l+r)/2;
		if (st<=m) update(2*nod, l, m);
		if (m<dr) update(2*nod+1, m+1, r);
	}
}

void query(int nod, int l, int r)
{
	if (ok) return;
	set <int>:: iterator it=arb[nod].lower_bound(a1);
	if (it!=arb[nod].end() && (*it)<=b1) ok=1;
	if (st<=l && r<=dr) 
	{
		it=arb2[nod].lower_bound(a1);
		if (it!=arb2[nod].end() && (*it)<=b1) ok=1;
	} else
	{
		int m=(l+r)/2;
		if (st<=m) query(2*nod, l, m);
		if (m<dr) query(2*nod+1, m+1, r);
	}
}

int main()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	scanf("%d %d %d",&n, &m, &q);
	int i, x, y, c;
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		u[y]=1;
	}
	for (i=1; i<=n; i++)
		if (!u[i])
			df(i);
	while (q--)
	{
		scanf("%d %d %d",&c, &x, &y);
		if (c==2)
		{
			st=a[x];
			dr=b[x];
			val=a[y];
			update(1, 1, n);
		} else
		{
			st=a[x];
			dr=b[x];
			a1=a[y];
			b1=b[y];
			ok=0;
			query(1, 1, n);
			if (ok) printf("YES\n"); else printf("NO\n");
		}
	}
}