Cod sursa(job #2134031)

Utilizator mihai.alphamihai craciun mihai.alpha Data 17 februarie 2018 15:53:17
Problema Gossips Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, q, st1, dr1, nr;
int f[100002], euler[100002][3];

vector <int> v[100002];
set <int> aint[524300], aint2[524300];

void dfs (int nod)
{
    nr ++;
    euler[nod][0] = nr;

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

    euler[nod][1] = nr;
}

void update (int nod, int st, int dr, int left, int right)
{
    aint[nod].insert (left);

    if (st1 <= st && dr <= dr1)
    {
        aint2[nod].insert (left);
        return;
    }

    int m = (st + dr) >> 1;

    if (st1 <= m)
        update (nod * 2, st, m, left, right);
    if (dr1 > m)
        update (nod * 2 + 1, m + 1, dr, left, right);
}

int query (int nod, int st, int dr, int left, int right)
{
    if (st1 <= st && dr <= dr1)
    {
        set <int> :: iterator it = aint[nod].lower_bound (left);
        if (it == aint[nod].end() || *it > right)
            return 0;
        return 1;
    }

    set <int> :: iterator it = aint2[nod].lower_bound (left);
    if (it != aint2[nod].end() && *it <= right)
        return 1;

    int m = (st + dr) >> 1, sol = 0;

    if (st1 <= m)
        sol += query (nod * 2, st, m, left, right);
    if (sol)
        return sol;

    if (dr1 > m)
        sol += query (nod * 2 + 1, m + 1, dr, left, right);
    return sol;
}

int main ()
{
    freopen ("gossips.in", "r", stdin);
    freopen ("gossips.out", "w", stdout);

    scanf ("%d %d %d", &n, &m, &q);

    int i, x, y, t;

    for (i = 1; i <= m; i ++)
    {
        scanf ("%d %d", &x, &y);

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

    for (i = 1; i <= n; i ++)
        if (!f[i])
            v[n + 1].push_back (i);

    dfs (n + 1);

    while (q --)
    {
        scanf ("%d %d %d", &t, &x, &y);

        st1 = euler[x][0];
        dr1 = euler[x][1];

        if (t == 1)
            printf ("%s\n", (query (1, 1, n + 1, euler[y][0], euler[y][1]) > 0) ? "YES" : "NO");
        else
            update (1, 1, n + 1, euler[y][0], euler[y][1]);
    }

    return 0;
}