Cod sursa(job #1929324)

Utilizator LucianTLucian Trepteanu LucianT Data 17 martie 2017 15:00:30
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 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;
class InputReader
{
public:
    InputReader() {}
    InputReader(const char *file_name){
        input_file=fopen(file_name,"r");
        cursor=0;
        fread(buffer,SIZE,1,input_file);
    }
    inline InputReader &operator >>(int &n)
    {
        while(buffer[cursor]<'0'||buffer[cursor]>'9')
            advance();
        n=0;
        while('0'<=buffer[cursor]&&buffer[cursor]<='9'){
            n=n*10+buffer[cursor]-'0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE=1<<17;
    int cursor;
    char buffer[SIZE];
    inline void advance()
    {
        ++cursor;
        if(cursor==SIZE){
            cursor=0;
            fread(buffer,SIZE,1,input_file);
        }
    }
};
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 xst,int xdr,int yst,int ydr)
{
    arbup[nod].insert(yst);
    if(xst<=st && dr<=xdr){
        arbdown[nod].insert(yst);
        return;
    }
    int mij=st+(dr-st)/2;
    if(xst<=mij)
        update(2*nod,st,mij,xst,xdr,yst,ydr);
    if(mij<xdr)
        update(2*nod+1,mij+1,dr,xst,xdr,yst,ydr);
}
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;
}
bool query(int nod,int st,int dr,int xst,int xdr,int yst,int ydr)
{
    auto it1=arbdown[nod].lower_bound(yst);
    if(it1!=arbdown[nod].end() && *it1<=ydr)
        return true;

    auto it2=arbup[nod].lower_bound(yst);
    if(it2==arbup[nod].end() || *it2>ydr)
        return false;

    int mij=st+(dr-st)/2;
    bool res=false;
    if(xst<=mij)
        res|=query(2*nod,st,mij,xst,xdr,yst,ydr);
    if(res)
        return true;
    if(mij<xdr)
        res|=query(2*nod+1,mij+1,dr,xst,xdr,yst,ydr);
    return res;
}
int main()
{
    InputReader f("gossips.in");
    freopen("gossips.out","w",stdout);
    //scanf("%d %d %d",&n,&m,&q);
    f>>n>>m>>q;
    for(i=1;i<=m;i++)
    {
        //scanf("%d %d",&x,&y);
        f>>x>>y;
        v[x].push_back(y);
        son[y]=true;
    }
    for(i=1;i<=n;i++)
        if(!son[i])
            dfs(i);
    while(q--)
    {
        f>>op>>x>>y;
        //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],last[y]);
    }
    return 0;
}