Cod sursa(job #1206892)

Utilizator misinozzz zzz misino Data 11 iulie 2014 13:57:09
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<fstream>
#include<set>
#include<vector>

#define N 200100

using namespace std;

ifstream f("gossips.in");
ofstream g("gossips.out");

int i,sol,mij,n,m,op,q,x,y,k,p[N],u[N],tata[N];

vector<int>v[N];

inline void dfs(int x){
    p[x] = ++ k;

    for(vector<int>::iterator it = v[x].begin() ; it != v[x].end() ; ++it)
        dfs(*it);

    u[x] = ++ k;
}

class SegmentTree{
public:
    set<int>s[N * 4],toate[N * 4];

    inline void update(int nod,int li,int ls,int st,int dr,int x){
        toate[nod].insert(x);
        if(st <= li && ls <= dr)
        {
            s[nod].insert(x);

            return ;
        }

        int mij = (li + ls) >> 1;

        if(st <= mij)
            update(nod << 1, li, mij, st, dr, x);

        if(mij < dr)
            update((nod << 1) | 1, mij + 1, ls, st, dr, x);
    }

    inline void query(int nod,int li,int ls,int st,int dr,int x,int y){
        set<int>::iterator it = s[nod].lower_bound(x);

        if(it != s[nod].end() && *it <= y)
        {
            sol = 1;

            return ;
        }

        it = toate[nod].lower_bound(x);

        if(li == ls || it == toate[nod].end() || *it > y)
            return;

        int mij = (li + ls) >> 1;

        if(st <= mij)
            query(nod << 1, li, mij, st, dr, x, y);

        if(mij < dr && !sol)
            query((nod << 1) | 1, mij + 1, ls, st, dr, x, y);
    }
};

SegmentTree aint;

int main()
{
    f >> n >> m >> q;

    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;

        tata[y] = x;
        v[x].push_back(y);
    }

    for(i = 1; i <= n; ++i)
        if(!tata[i])
            dfs(i);

    for(i = 1; i <= q; ++i)
    {
        f >> op >> x >> y;

        if(op == 2)
        {
            aint.update(1,1,k,p[x],u[x],p[y]);
        }
        else
        {
            sol = 0;

            aint.query(1,1,k,p[x],u[x],p[y],u[y]);

            if(sol == 1)
                g << "YES\n";
            else
                g << "NO\n";
        }
    }
    return 0;
}