Cod sursa(job #547519)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 martie 2011 14:05:31
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.07 kb
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define N 100010
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >
#define pib pair< int,bool >
#define pb push_back
#define ll long long

int n,m,Q;
vector< int > a[N];
int t[N];
pii inter[N];
pii interf[N];
int nfr;
int v[N];
set< pii > b[3*N];
int pr,ul;
pii val;
bool ret;

inline void citire() {
	scanf("%d%d%d",&n,&m,&Q);
	
	int x,y;
	for(int i=0; i<m; ++i) {
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		t[y] = x;
	}
}

void dfs(int nod) {
	v[++v[0]] = nod;
	inter[nod].fs = v[0];
	interf[nod].fs = nfr+1;
	if(a[nod].empty()) {
		++nfr;
		inter[nod].sc = v[0];
		interf[nod].sc = nfr;
		return;
	}
	
	for(size_t i=0,lim=a[nod].size(); i<lim; ++i)
		dfs(a[nod][i]);
	
	inter[nod].sc = v[0];
	interf[nod].sc = nfr;
}
	
inline void precalc() {
	for(int i=1; i<=n; ++i) {
		if(t[i]==0)
			dfs(i);
	}
}

void query(int p,int u,int i) {
	if(p>u)
		return;
	
	if(pr<=p && u<=ul) {
		if(b[i].empty())
			return;
		set< pii >::iterator it = b[i].lower_bound(mp(val.fs,0));
		if(it==b[i].end()) {
			--it;
			if((it->sc)>=val.fs) {
				ret = true;
				return;
			}
		} else
		if((it->fs)>val.fs) {
		        if((it->fs)<=val.sc) {
				ret = true;
				return;
			}    
			if(it!=b[i].begin()) {
				--it;
				if((it->sc)>=val.fs) {
					ret = true;
					return;
				}
			}
		} else {
			ret = true;
			return;
		}
		
		it = b[i].lower_bound(mp(val.sc,0));
		if(it==b[i].end()) {
			--it;
			if((it->sc)>=val.sc) {
				ret = true;
				return;
			}
		} else
		if((it->fs)>val.sc) {
			if(it!=b[i].begin()) {
				--it;
				if((it->sc)>=val.sc) {
					ret = true;
					return;
				}
			}
		} else {
			ret= true;
			return;
		}
		
		return;
	}
	
	int m = (p+u)>>1;
	if(pr<=m)
		query(p,m,(i<<1));
	if(m<ul && ret==false)
		query(m+1,u,((i<<1)+1));
}

void update(int p,int u,int i) {
	if(p>u)
		return;
	
	if(!b[i].empty()) {
		set< pii >:: iterator it1,it2,it;
	
		it1 = b[i].lower_bound(mp(val.fs,0));
		for(it2=it1; it2!=b[i].end() && (it2->sc)<=val.sc; ++it2)
			;
		if(it2!=it1)
			b[i].erase(it1,it2);
		
		if(b[i].empty())
			b[i].insert(val);
		else {
			pii aux1,aux2;
			it = b[i].lower_bound(mp(val.fs,0));
			
			if(it==b[i].end()) {
				--it;
				aux1 = (*it);
				if(aux1.sc>=val.fs) {
					if(aux1.sc>=val.sc)
						;
					else {
						b[i].erase(it);
						b[i].insert(mp(aux1.fs,val.sc));
					}
				} else
					b[i].insert(val);
			} else
			if((it->fs)>val.fs) {
				if(it==b[i].begin()) {
					aux1 = (*it);
					if(aux1.fs<=val.sc) {
						b[i].erase(it);
						b[i].insert(mp(val.fs,max(aux1.sc,val.sc)));
					} else
						b[i].insert(val);
				} else {
					it2 = it;
					--it;
					it1 = it;
					aux1 = (*it1);
					aux2 = (*it2);
					
					if(val.fs<=aux1.sc && aux2.fs<=val.sc) {
						++it2;
						b[i].erase(it1,it2);
						b[i].insert(mp(aux1.fs,max(aux2.sc,val.sc)));
					} else
					if(val.fs<=aux1.sc) {
						b[i].erase(it1);
						b[i].insert(mp(aux1.fs,max(aux1.sc,val.sc)));
					} else
					if(aux2.fs<=val.sc) {
						b[i].erase(it2);
						b[i].insert(mp(val.fs,max(aux2.sc,val.sc)));
					} else
						b[i].insert(val);
				}
			} else {
				if((it->sc)<val.sc) {
					b[i].erase(it);
					b[i].insert(val);
				}
			}
		}
	} else
		b[i].insert(val);
	
	
	if(p==u) 
		return;
	
	int m = (p+u)>>1;
	
	if(pr<=m)
		update(p,m,(i<<1));
	else
		update(m+1,u,((i<<1)+1));
}

inline void rezolva() {
	int cod,x,y;
	
	for(int i=0; i<Q; ++i) {
		scanf("%d%d%d",&cod,&x,&y);
		
		if(cod==1) {
			ret = false;
			pr = inter[y].fs;
			ul = inter[y].sc;
			val = interf[x];			
			query(1,n,1);
			if(ret)
				fputs("YES\n",stdout);
			else
				fputs("NO\n",stdout);
		} else {
			pr = inter[y].fs;
			val = interf[x];
			update(1,n,1);
		}
	}
}

int main() {
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	
	citire();
	precalc();
	rezolva();
	
	return 0;
}