Cod sursa(job #556444)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 16 martie 2011 09:50:49
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#include <vector>
#include <set>
#include <queue>
using namespace std;
#define N_MAX 100010
#define FOR(i, v) for(typeof(v.begin()) i = v.begin(); i != v.end(); ++i)
vector <int> G[N_MAX];
set <int> H[3*N_MAX], H2[3*N_MAX];
set <int> ::iterator it;
int in[N_MAX], out[N_MAX];
int viz[N_MAX], que[N_MAX];
int n, m, k, op;
int a, b, val, A, B;
void df(int x) {
	viz[x] = 1;
	if(op) in[x] = ++k;
	FOR(i, G[x]) 
		if(!viz[*i])
			df(*i);
	if(op) out[x] = k;
	if(!op) que[++que[0]] = x;
}
void liniarizare() {
	for(int i = 1; i <= n; ++i)
		if(!viz[i])
			df(i);
	memset(viz, 0, (n+3)*sizeof(viz[0]));
	op = 1; // liniarizez acum
	for(int i = que[0]; i; --i)
		if(!viz[que[i]]) 
			df(que[i]);
}
void update(int p, int q, int i){
	H[i].insert(val);
	if(a <= p && q <= b){
		H2[i].insert(val);
		return ;
	}
	int m = (p+q)/2;
	if(a <= m) update(p, m, 2*i);
	if(b > m) update(m+1, q, 2*i+1);
}
void query(int p, int q, int i){
	if(val) return;
	
	it = H2[i].lower_bound(A);
	if(it != H2[i].end() && *it <= B) val = 1;
	
	if(a <= p && q <= b){
		it = H[i].lower_bound(A);
		if(it != H[i].end() && *it <= B) val = 1;
		return;
	}
	int m = (p+q)/2;
	if(a <= m) query(p, m, 2*i);
	if(b > m) query(m+1, q, 2*i+1);
}
int main() {
	freopen("gossips.in", "r", stdin);
	freopen("gossips.out", "w", stdout);
	int q;
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1;  i<= m; ++i){
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
	}
	liniarizare();
	for(int i = 1; i <= q; ++i){
		int c, x, y;
		scanf("%d%d%d", &c, &x, &y);
		if(c == 2){
			a = in[x]; b = out[x];
			val = in[y];
			update(1, n, 1);
		}
		else {
			a = in[x]; b = out[x];
			val = 0;
			A = in[y]; B = out[y];
			query(1, n, 1);
			if(val) printf("YES\n");
			else printf("NO\n");
		}
	}
	
	return 0;
}