Cod sursa(job #562543)

Utilizator katakunaCazacu Alexandru katakuna Data 23 martie 2011 12:40:27
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;

#define Nmax 100010

int n, m, q, N, X, Y, A, B, val, POZ;
int Tata[Nmax], St[Nmax], Dr[Nmax];
set <int> AI[4 * Nmax], AD[4 * Nmax];
vector <int> V[Nmax];

void citire () {
	
	int i, x, y;
	
	scanf ("%d %d %d", &n, &m, &q);
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		V[x].push_back (y);
		Tata[y] = x;
	}
}

void dfs (int nod) {
	
	St[nod] = ++N;
	for (vector <int>::iterator it = V[nod].begin (); it != V[nod].end (); it++) 
		if (!St[*it]) dfs (*it);
	Dr[nod] = N;
}

#define MIJ ((st + dr) >> 1)
#define N1 (nod << 1)
#define N2 ((nod << 1) + 1)

void update (int nod, int st, int dr) {
	
	AI[nod].insert (val);
	
	if (A <= st && dr <= B) {
		AD[nod].insert (val);
		return ;
	}
	
	if (A <= MIJ) update (N1, st, MIJ);
	if (MIJ < B) update (N2, MIJ + 1, dr);
}

int query (int nod, int st, int dr) {
	
	set <int>::iterator it;
	it = AD[nod].lower_bound (A);
	if (it != AD[nod].end () && *it <= B) return 1;
	
	it = AI[nod].lower_bound (A);
	if (it != AI[nod].end () && *it <= B) {
		if (X <= st && dr <= Y) return 1;
		if (X <= MIJ) 
			if (query (N1, st, MIJ)) return 1;
		if (MIJ < Y) return query (N2, MIJ + 1, dr);
	}
	
	return 0;
}

int main () {

	freopen ("gossips.in", "r", stdin);
	freopen ("gossips.out", "w", stdout);
	
	citire ();
	
	int i, tip, x, y;
	for (i = 1; i <= n; i++)
		if (!Tata[i]) 
			dfs (i);
	
	for (i = 1; i <= q; i++) {
		scanf ("%d %d %d", &tip, &x, &y);
		if (tip == 2) {
			A = St[x]; B = Dr[x]; val = St[y];
			update (1, 1, N);
		}
		else {
			X = St[x]; Y = Dr[x]; A = St[y]; B = Dr[y];
			if (query (1, 1, N))
				printf ("YES\n");
			else
				printf ("NO\n");
		}
	}
	
	return 0;
}