Cod sursa(job #1776446)

Utilizator akaprosAna Kapros akapros Data 11 octombrie 2016 12:23:49
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
#define maxN 100002
#define SetIt set < int > :: iterator
using namespace std;
int n, m, q, cnt, val, ux, uy, vx, vy;
int l[maxN], r[maxN];
bool f[maxN];
set < int > st[4 * maxN], St[4 * maxN];
vector < int > V[maxN];
void dfs(int x)
{
    int i, nod;
    l[x] = ++ cnt;
    for (i = 0; i < V[x].size(); ++ i)
        if (!l[nod = V[x][i]])
            dfs(nod);
    r[x] = cnt;
}
void update(int nod, int x, int y)
{
    if (x > y)
        return ;
    St[nod].insert(val);
    if (ux <= x && uy >= y)
    {
        st[nod].insert(val);
        return ;
    }
    int mid = (x + y) >> 1,
        lson = 2 * nod,
        rson = 2 * nod;
    if (mid >= ux)
        update(lson, x, mid);
    if (mid < uy)
        update(rson, mid + 1, y);
}
int query(int nod, int x, int y)
{
    SetIt it = st[nod].lower_bound(vx);
    if (it != st[nod].end() && (*it) <= vy)
        return 1;
    int mid = (x + y) >> 1,
        lson = 2 * nod,
        rson = 2 * nod;
    it = St[nod].lower_bound(vx);
    if (it != St[nod].end() && (*it) <= vy)
    {
        if (ux <= x && uy >= y)
            return 1;
        if (mid >= ux && query(lson, x, mid))
            return 1;
        if (mid < uy)
            return query(rson, mid + 1, y);
    }
    return 0;
}
void read()
{
    freopen("gossips.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &q);
    while (m --)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        V[x].push_back(y);
        f[y] = 1;
    }
}
void solve()
{
    int i;
    for (i = 1; i <= n; ++ i)
        if (!f[i])
            dfs(i);
}
void write()
{
    freopen("gossips.out", "w", stdout);
    while (q --)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);
        if (t == 1)
        {
            ux = l[x];
            uy = r[x];
            vx = l[y];
            vy = r[y];
            if (query(1, 1, n))
                printf("YES\n");
            else
                printf("NO\n");
        }
        else
        {
            ux = l[x];
            uy = r[x];
            val = l[y];
            update(1, 1, n);
        }
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}