Cod sursa(job #673005)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 februarie 2012 17:33:17
Problema Gossips Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<fstream>
#include<vector>
#include<set>

#define maxn 100005
#define pb push_back

using namespace std;

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

int n,m,op,i,x,y,a,b,lim1,lim2,p,tip;
int gr_in[maxn],lEft[maxn],rIght[maxn];
vector<int>G[maxn];
set<int>Arb[4*maxn],Ad[4*maxn];
set<int>::iterator itt;

void dfs ( int nod ){
	
	lEft[nod] = ++p;
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		dfs(*itt);
	}
	rIght[nod] = p;
}

void update ( int nod , int st , int dr ){
	Arb[nod].insert(y);
	
	if ( a <= st && dr <= b ){
		Ad[nod].insert(y);
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( a <= mij ){
		update(nodst,st,mij);
	}
	if ( b > mij ){
		update(noddr,mij+1,dr);
	}
}

int query ( int nod , int st , int dr ){
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	itt = Ad[nod].lower_bound(lim1);
	if ( itt != Ad[nod].end() && (*itt) <= lim2 ){
		return 1;
	}
	
	itt = Arb[nod].lower_bound(lim1);
	if ( itt != Arb[nod].end() && (*itt) <= lim2 ){
		if ( a <= st && dr <= b ){
			return 1;
		}
		if ( a <= mij ){
			if ( query(nodst,st,mij) )
				return 1;
		}
		if ( b > mij ){
			return query(noddr,mij+1,dr);
		}
	}
	
	return 0;
}

int main () {
	
	f >> n >> m >> op;
	
	for ( i = 1 ; i <= m ; ++i ){
		f >> x >> y;
		++gr_in[y]; G[x].pb(y);
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( !gr_in[i] ){
			dfs(i);
		}
	}
	
	for ( int ii = 1 ; ii <= op ; ++ii ){
		f >> tip >> x >> y;
		
		if ( tip == 2 ){
			a = lEft[x]; b = rIght[x]; y = lEft[y];
			update(1,1,n);
		}
		else{
			a = lEft[x]; b = rIght[x]; lim1 = lEft[y]; lim2 = rIght[y];
			if ( query(1,1,n) ){
				g << "YES\n";
			}
			else{
				g << "NO\n";
			}
		}
	}
	
	f.close();
	g.close();
	
	return 0;
}