Cod sursa(job #1209832)

Utilizator misinozzz zzz misino Data 18 iulie 2014 19:17:07
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<fstream>
#include<vector>
#include<set>

#define N 100100

using namespace std;

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

int n,m,q,i,ok,x,y,op,k,t[N],p[2 * N],u[2 * N];

vector<int>v[N];

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

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

    u[x] = ++k;
}

class aint{
public:

    set<int>toate[8 * N],sol[8 * N];

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

        if(st <= li && ls <= dr)
        {
            sol[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 = sol[nod].lower_bound(x);

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

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

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

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

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

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

aint a;

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

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

        t[y] = x;

        v[x].push_back(y);
    }

    for(i = 1 ; i <= n ; ++i)
        if(!t[i])
            dfs(i, 0);

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

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

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

            if(ok) g << "YES\n";
            else g << "NO\n";
        }
    }

    return 0;
}