Cod sursa(job #1929317)

Utilizator LucianTLucian Trepteanu LucianT Data 17 martie 2017 14:50:04
Problema Gossips Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
#define maxN 100005
using namespace std;
bool son[maxN];
bool seen[maxN];
int n,m,q,i,j,x,y,op;
vector<int>v[maxN];

set<int> arbup[8*maxN],arbdown[8*maxN];
int first[maxN],last[maxN],lin;
void dfs(int nod) /* linearisation dfs */
{
    first[nod]=++lin;
    for(auto it:v[nod])
        dfs(it);
    last[nod]=++lin;
}
void update(int nod,int st,int dr,int x,int y,int val)
{
    if(x<=st && dr<=y){
        arbdown[nod].insert(val);
        arbup[nod].insert(val);
        return;
    }

    int mij=st+(dr-st)/2;
    arbdown[nod].insert(val);
    if(x<=mij)
        update(2*nod,st,mij,x,y,val);
    if(mij<y)
        update(2*nod+1,mij+1,dr,x,y,val);
}
inline bool searchInterval(set<int>Set,int x,int y)
{
    auto it=Set.lower_bound(x);
    if(it==Set.end() || *it>y)
        return false;
    return true;
}
int query(int nod,int st,int dr,int xst,int xdr,int yst,int ydr)
{
    if(xst<=st && dr<=xdr)
        return searchInterval(arbdown[nod],yst,ydr);

    if(searchInterval(arbup[nod],yst,ydr))
        return true;

    int mij=st+(dr-st)/2;
    bool res=false;
    if(xst<=mij)
        res|=query(2*nod,st,mij,xst,xdr,yst,ydr);
    if(mij<xdr)
        res|=query(2*nod+1,mij+1,dr,xst,xdr,yst,ydr);
    return res;
}
int main()
{
    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);
        v[x].push_back(y);
        son[y]=true;
    }
    for(i=1;i<=n;i++)
        if(!son[i])
            dfs(i);
    while(q--)
    {
        scanf("%d %d %d",&op,&x,&y);
        if(op==1){
            bool res=query(1,1,lin,first[x],last[x],first[y],last[y]);
            if(res)
                printf("YES\n");
            else printf("NO\n");
        }
        else
            update(1,1,lin,first[x],last[x],first[y]);
    }
    return 0;
}