Cod sursa(job #673001)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 februarie 2012 17:28:54
Problema Gossips Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<stdio.h>
#include<vector>
#include<set>

#define maxn 100005
#define pb push_back

using namespace std;

FILE*f=fopen("gossips.in","r");
FILE*g=fopen("gossips.out","w");

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 () {
	
	fscanf(f,"%d %d %d",&n,&m,&op);
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&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 ){
		fscanf(f,"%d %d %d",&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) ){
				fprintf(g,"YES\n");
			}
			else{
				fprintf(g,"NO\n");
			}
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}