Cod sursa(job #2134034)

Utilizator mihai.alphamihai craciun mihai.alpha Data 17 februarie 2018 15:58:35
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 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[300000], aint2[300000];

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;
}

#define BUF 1 << 17

char buf[BUF];
int pos = BUF;

inline char next()
{
    if(pos == BUF)
        fread(buf, 1, BUF, stdin), pos = 0;

    return buf[pos++];
}

inline int read()
{
    int x = 0;
    char ch = next();

    while(!isdigit(ch))
        ch = next();

    while(isdigit(ch))
        x = x * 10 + ch - '0', ch = next();

    return x;
}

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

    n = read(), m = read(), q = read();

    int i, x, y, t;

    for (i = 1; i <= m; i ++)
    {
        x = read(), y = read();

        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 --)
    {
        t = read(), x = read(), y = read();

        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;
}