Cod sursa(job #543847)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 28 februarie 2011 17:39:18
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>

#include <set>
#include <vector>

using namespace std;

int n, m, q, st1, dr1, nr;
int f[100002], euler[100002][3];

vector <int> v[100002];
set <int> aint[524300], aint2[524300];

void dfs (int nod)
{
	nr ++;
	euler[nod][0] = nr;
	
	for (vector <int> :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
		dfs (*it);
	
	euler[nod][1] = nr;
}

void update (int nod, int st, int dr, int left, int right)
{
	aint[nod].insert (left);
	
	if (st1 <= st && dr <= dr1)
	{
		aint2[nod].insert (left);
		return;
	}
	
	int m = (st + dr) >> 1;
	
	if (st1 <= m)
		update (nod * 2, st, m, left, right);
	if (dr1 > m)
		update (nod * 2 + 1, m + 1, dr, left, right);
}

int query (int nod, int st, int dr, int left, int right)
{
	if (st1 <= st && dr <= dr1)
	{
		set <int> :: iterator it = aint[nod].lower_bound (left);
		if (it == aint[nod].end() || *it > right)
			return 0;
		return 1;
	}
	
	set <int> :: iterator it = aint2[nod].lower_bound (left);
	if (it != aint2[nod].end() && *it <= right)
		return 1;
	
	int m = (st + dr) >> 1, sol = 0;
	
	if (st1 <= m)
		sol += query (nod * 2, st, m, left, right);
	if (sol)
		return sol;
	
	if (dr1 > m)
		sol += query (nod * 2 + 1, m + 1, dr, left, right);
	return sol;
}

int main ()
{
	freopen ("gossips.in", "r", stdin);
	freopen ("gossips.out", "w", stdout);
	
	scanf ("%d %d %d", &n, &m, &q);
	
	int i, x, y, t;
	
	for (i = 1; i <= m; i ++)
	{
		scanf ("%d %d", &x, &y);
		
		v[x].push_back (y);
		f[y] = 1;
	}
	
	for (i = 1; i <= n; i ++)
		if (!f[i])
			v[n + 1].push_back (i);
		
	dfs (n + 1);
	
	while (q --)
	{
		scanf ("%d %d %d", &t, &x, &y);
		
		st1 = euler[x][0];
		dr1 = euler[x][1];
		
		if (t == 1)
			printf ("%s\n", (query (1, 1, n + 1, euler[y][0], euler[y][1]) > 0) ? "YES" : "NO");
		else
			update (1, 1, n + 1, euler[y][0], euler[y][1]);
	}
	
	return 0;
}