Cod sursa(job #561407)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 20 martie 2011 10:33:48
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <set>
#include <vector>
#define Nmax 100002
#define pb push_back
using namespace std;

int F[Nmax],L[Nmax],sh[Nmax];
vector< int > v[Nmax];
set< int > A_toti[Nmax*4],  A_unii[Nmax*4];
int N,M,Q,nr;

inline void df(int x){
    vector< int >:: iterator it;
    F[x] = ++nr;
    for(it=v[x].begin(); it!=v[x].end(); ++it)
        if( !F[*it] ) df(*it);
    L[x] = nr;
}

inline void Update(int nod,int l,int r,int x,int y,int val){
    A_unii[nod].insert(val);

    if( x<=l && r<=y ){
        A_toti[nod].insert(val);
        return;
    }

    int m=l+(r-l)/2;
    if( x<=m ) Update(nod*2,l,m,x,y,val);
    if( m<y ) Update(nod*2+1,m+1,r,x,y,val);
}

inline int Query(int nod,int l,int r,int xi,int yi,int xj,int yj){
    set< int >:: iterator it;
    it = A_toti[nod].lower_bound(xj);
    if( it != A_toti[nod].end() && *it <= yj ) return 1;

    it = A_unii[nod].lower_bound(xj);
    if( it == A_unii[nod].end() || *it>yj ) return 0;
    if( xi<=l && r<=yi ){
        if( *it <= yj ) return 1;
        return 0;
    }

    int m=l+(r-l)/2;
    if( xi<=m ){
        if( Query(nod*2,l,m,xi,yi,xj,yj) ) return 1;
    }
    if( m<yi ) return Query(nod*2+1,m+1,r,xi,yi,xj,yj);
    return 0;
}

int main(){
    int i,x,y,tip;
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    scanf("%d%d%d",&N,&M,&Q);
    for(i=1;i<=M;++i){
        scanf("%d%d",&x,&y);
        sh[y]=1;
        v[x].pb(y);
    }

    for(i=1;i<=N;++i)
        if( !sh[i] ) df(i);

    for(i=1;i<=Q;++i){
        scanf("%d%d%d",&tip,&x,&y);
        if( tip == 2 ){
            Update(1,1,N,F[x],L[x],F[y]);
        }
        else{
            if( Query(1,1,N,F[x],L[x],F[y],L[y]) ) printf("YES\n");
            else printf("NO\n");
        }
    }

    fclose(stdin); fclose(stdout);
    return 0;
}