Cod sursa(job #792860)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 1 octombrie 2012 15:50:46
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<vector>
#include<set>
using namespace std;

ifstream in("gossips.in");
ofstream out("gossips.out");

const int N = 100100;

int n, nr, m, q, ver[N], l[N], r[N], px, py, val, vx, vy;
vector<int> v[N];
set<int> arbPart[3*N], arbAll[3*N];

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

void update(int nod, int pozx, int pozy) {
	arbPart[nod].insert(val);
	
	if(px <= pozx && pozy <= py) {
		arbAll[nod].insert(val);
		return;
	}
	
	int mid = (pozx + pozy)/2;
	
	if(mid >= px)
		update(2 * nod, pozx, mid);
	if(mid < py)
		update(2 * nod + 1, mid + 1, pozy);
}

bool query(int nod, int pozx, int pozy) {
	
	set<int>::iterator it = arbAll[nod].lower_bound(vx);
	if(it != arbAll[nod].end() && (*it) <= vy)
		return true;
	
	it = arbPart[nod].lower_bound(vx);
	if(it != arbPart[nod].end() && (*it) <= vy) {
		int mid = (pozx + pozy)/2;
		
		if(px <= pozx && pozy <= py)
			return true;
		
		if(mid >= px)
			if(query(2 * nod, pozx, mid))
				return true;
		if(mid < py)
			return query(2 * nod + 1, mid + 1, pozy);
	}
	
	return false;
}

int main() {
	int i, a, b, op, x, y;
	
	in >> n >> m >> q;
	
	for(i = 1; i<=m; ++i) {
		in >> a >> b;
		ver[b] = true;
		v[a].push_back(b);
	}
	
	for(i = 1; i<=n; ++i) if(!ver[i])
		dfs(i);
	
	for(i = 1; i<=q; ++i) {
		in >> op >> x >> y;
		
		if(op == 1) {
			px = l[x]; py = r[x];
			vx = l[y]; vy = r[y];
			
			out << (query(1, 1, n) ? "YES\n" : "NO\n");
		}
		else {
			px = l[x]; py = r[x]; val = l[y];
			
			update(1, 1, n);
		}
	}
	
	return 0;
}