Cod sursa(job #1800411)

Utilizator touristGennady Korotkevich tourist Data 7 noiembrie 2016 19:22:43
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair <int,int>
#define mp make_pair
#define fi first
#define se second
#define Nmax 100005

using namespace std;

vector <int> L[Nmax];
int n,q,cnt[Nmax],poz[Nmax],l;
bool bad[Nmax],Good;
set <int> aintUp[4*Nmax],aintDown[4*Nmax];

inline void Dfs(int nod)
{
    poz[nod]=++l;
    for(auto it : L[nod])
    {
        Dfs(it);
        cnt[nod]+=1+cnt[it];
    }
}

inline void Update(int nod, int st, int dr, int x, int y, int val)
{
    aintUp[nod].insert(val);
    if(st==x && y==dr)
    {
        aintDown[nod].insert(val);
        return;
    }
    int mij=((st+dr)>>1);
    if(y<=mij) Update(2*nod,st,mij,x,y,val);
    else
        if(x>mij) Update(2*nod+1,mij+1,dr,x,y,val);
        else
        {
            Update(2*nod,st,mij,x,mij,val);
            Update(2*nod+1,mij+1,dr,mij+1,y,val);
        }
}

inline bool Ok(int v1, int v2, set<int> Q)
{
    set<int>::iterator it = Q.lower_bound(v1);
    if(it==Q.end()) return 0;
    return ((*it) <= v2);
}

inline void Query(int nod, int st, int dr, int x, int y, int v1, int v2)
{
    if(Good) return;
    if(Ok(v1,v2,aintDown[nod]))
    {
        Good=1; return;
    }
    if(st==x && y==dr)
    {
        if(Ok(v1,v2,aintUp[nod])) Good=1;
        return;
    }
    int mij=((st+dr)>>1);
    if(y<=mij) Query(2*nod,st,mij,x,y,v1,v2);
    else
        if(x>mij) Query(2*nod+1,mij+1,dr,mij+1,y,v1,v2);
        else
        {
            Query(2*nod,st,mij,x,mij,v1,v2);
            Query(2*nod+1,mij+1,dr,mij+1,y,v1,v2);
        }
}

int main()
{
    int m,x,y,i,tip,k=0;
    ifstream cin("gossips.in");
    ofstream cout("gossips.out");
    cin>>n>>m>>q;
    while(m--)
    {
        cin>>x>>y;
        L[x].pb(y);
        bad[y]=1;
    }

    for(i=1;i<=n;++i)
        if(!bad[i]) Dfs(i);

    for(i=1;i<=q;++i)
    {
        cin>>tip>>x>>y;
        if(tip==1)
        {
            Good=0;
            Query(1,1,n,poz[x],poz[x]+cnt[x],poz[y],poz[y]+cnt[y]);
            if(Good) cout<<"YES\n";
            else cout<<"NO\n";
        }
        else
            Update(1,1,n,poz[x],poz[x]+cnt[x],poz[y]);
    }
    return 0;
}