Cod sursa(job #543908)

Utilizator DraStiKDragos Oprica DraStiK Data 28 februarie 2011 18:41:03
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

#define lb lower_bound
#define ub upper_bound
#define pb push_back

#define DIM 100005

set <int> aint_cnt[DIM<<2],aint_val[DIM<<2];
int t[DIM],fs[DIM],ls[DIM];
vector <int> g[DIM];
int N,M,P,Q;

void read ()
{
    int i,x,y;

    scanf ("%d%d%d",&N,&M,&Q);
    for (i=1; i<=M; ++i)
    {
        scanf ("%d%d",&x,&y);
        g[x].pb (y);
        t[y]=x;
    }
}

void df (int nod)
{
    vector <int> :: iterator it;

    fs[nod]=++P;
    for (it=g[nod].begin (); it!=g[nod].end (); ++it)
        df (*it);
    ls[nod]=P;
}

void update (int nod,int st,int dr,int in,int sf,int poz)
{
    int mij;

    aint_cnt[nod].insert (poz);
    if (in<=st && dr<=sf)
        aint_val[nod].insert (poz);
    else
    {
        mij=(st+dr)>>1;

        if (in<=mij)
            update (nod<<1,st,mij,in,sf,poz);
        if (mij<sf)
            update ((nod<<1)|1,mij+1,dr,in,sf,poz);
    }
}

int query (int nod,int st,int dr,int in,int sf,int poz_st,int poz_dr)
{
    int mij,ok;

    if (in<=st && dr<=sf)
    {
        if (aint_cnt[nod].lb (poz_st)!=aint_cnt[nod].ub (poz_dr))
            return 1;
        return 0;
    }

    if (aint_val[nod].lb (poz_st)!=aint_val[nod].ub (poz_dr))
        return 1;

    ok=0; mij=(st+dr)>>1;
    if (in<=mij)
        ok|=query (nod<<1,st,mij,in,sf,poz_st,poz_dr);
    if (mij<sf)
        ok|=query ((nod<<1)|1,mij+1,dr,in,sf,poz_st,poz_dr);
    return ok;
}

void solve ()
{
    int i,tip,x,y;

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

    for (i=1; i<=Q; ++i)
    {
        scanf ("%d%d%d",&tip,&x,&y);

        if (tip==2)
            update (1,1,N,fs[x],ls[x],fs[y]);
        else
            if (query (1,1,N,fs[x],ls[x],fs[y],ls[y]))
                printf ("YES\n");
            else
                printf ("NO\n");
    }
}

int main ()
{
    freopen ("gossips.in","r",stdin);
    freopen ("gossips.out","w",stdout);

    read ();
    solve ();

    return 0;
}