Cod sursa(job #987888)

Utilizator darrenRares Buhai darren Data 21 august 2013 17:07:54
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int N, M, Q;
vector<int> V[100002];
int in[100002], out[100002], isnow;
bool isson[100002];

set<int> ARB[4 * 200002], T[4 * 200002];
int Ap1, Ap2, Av, Ar1, Ar2, Ar;

void update(int nod, int i1, int i2)
{
    T[nod].insert(Av);
    if (Ap1 <= i1 && i2 <= Ap2)
    {
        ARB[nod].insert(Av);
        return;
    }

    int mid = (i1 + i2) / 2;
    if (Ap1 <= mid) update(nod * 2, i1, mid);
    if (Ap2 > mid) update(nod * 2 + 1, mid + 1, i2);
}
void query(int nod, int i1, int i2)
{
    set<int>::iterator it = ARB[nod].lower_bound(Ar1);
    if (it != ARB[nod].end() && *it <= Ar2)
    {
        Ar = 1;
        return;
    }

    if (i1 == i2 || T[nod].lower_bound(Ar1) == T[nod].end() || (*T[nod].lower_bound(Ar1)) > Ar2) return;

    int mid = (i1 + i2) / 2;
    if (Ap1 <= mid) query(nod * 2, i1, mid);
    if (Ap2 > mid && !Ar) query(nod * 2 + 1, mid + 1, i2);
}

void Dfs(int x)
{
    in[x] = ++isnow;
    for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
        Dfs(*it);
    out[x] = ++isnow;
}

int main()
{
    ifstream fin("gossips.in");
    ofstream fout("gossips.out");

    fin >> N >> M >> Q;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1].push_back(nod2);
        isson[nod2] = true;
    }

    for (int i = 1; i <= N; ++i)
        if (!isson[i])
            Dfs(i);

    for (int i = 1, type, val1, val2; i <= Q; ++i)
    {
        fin >> type >> val1 >> val2;
        if (type == 1)
        {
            Ap1 = in[val1], Ap2 = out[val1], Ar1 = in[val2], Ar2 = out[val2], Ar = 0;
            query(1, 1, 2 * N);

            if (Ar) fout << "YES\n";
            else    fout << "NO\n";
        }
        else
        {
            Ap1 = in[val1], Ap2 = out[val1], Av = in[val2];
            update(1, 1, 2 * N);
        }
    }

    fin.close();
    fout.close();
}