Cod sursa(job #1389456)

Utilizator geniucosOncescu Costin geniucos Data 16 martie 2015 11:47:43
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<cstdio>
#include<vector>
#include<set>

using namespace std;

int nr, N, M, N_Q, st[100009], dr[100009];
bool fiu[100009], Ok;

vector < int > fii[100009];
set < int > arb_sub[800009], arb_up[800009];

bool between (int left, int right, set < int > &curr)
{
    set < int > :: iterator it = curr.lower_bound (left);
    if (it == curr.end())
        return 0;
    if (*it > right)
        return 0;
    return 1;
}

void U (int nod, int st, int dr, int x, int y, int val)
{
    arb_up[nod].insert (val);
    if (x <= st && dr <= y)
    {
        arb_sub[nod].insert (val);
        return ;
    }

    int mij = (st + dr) >> 1;
    if (x <= mij)
        U (nod<<1, st, mij, x, y, val);
    if (y > mij)
        U ((nod<<1) + 1, mij + 1, dr, x, y, val);
}

void Q (int nod, int st, int dr, int x, int y, int st_val, int dr_val)
{
    if (Ok)
        return ;

    if (between (st_val, dr_val, arb_sub[nod]))
    {
        Ok = 1;
        return ;
    }

    if (x <= st && dr <= y)
    {
        if (between (st_val, dr_val, arb_up[nod]))
            Ok = 1;
        return ;
    }

    int mij = (st + dr) >> 1;
    if (x <= mij)
        Q (nod<<1, st, mij, x, y, st_val, dr_val);
    if (y > mij)
        Q ((nod<<1) + 1, mij + 1, dr, x, y, st_val, dr_val);
}

void dfs (int nod)
{
    st[nod] = ++nr;
    for (vector < int > :: iterator it = fii[nod].begin(); it != fii[nod].end(); it ++)
        dfs (*it);
    dr[nod] = ++nr;
}

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

scanf ("%d %d %d", &N, &M, &N_Q);

while (M)
{
    M --;
    int x, y;
    scanf ("%d %d", &x, &y);
    fiu[y] = 1;
    fii[x].push_back (y);
}

for (int i=1; i<=N; i++)
    if (fiu[i] == 0)
        dfs (i);

while (N_Q)
{
    N_Q --;
    int tip, x, y;
    scanf ("%d %d %d", &tip, &x, &y);
    if (tip == 1)
    {
        Ok = 0;
        Q (1, 1, nr, st[x], dr[x], st[y], dr[y]);
        if (Ok)
            printf ("YES\n");
        else
            printf ("NO\n");
    }
    else
        U (1, 1, nr, st[x], dr[x], st[y]);
}

return 0;
}