Cod sursa(job #543701)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 28 februarie 2011 15:07:31
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

#define maxn 100010

int n, m, q, i, j, k, a, b, t;
int st[maxn], dr[maxn], f[maxn], tata[maxn];
set<int> dir[3*maxn], ind[3*maxn];
vector<int> v[maxn];

void df(int nod)
{
    f[nod]=1;
    st[nod]=++t;
    for(int j=0; j<v[nod].size(); ++j)
        df(v[nod][j]);
    dr[nod]=t;
}

void update(int nod, int left, int right, int ileft, int iright, int val)
{
    ind[nod].insert(val);
    if(ileft<=left && right<=iright)
    {
        dir[nod].insert(val);
        return;
    }
    int med=(left+right)/2;
    if(ileft<=med)
        update(nod*2, left, med, ileft, iright, val);
    if(med<iright)
        update(nod*2+1, med+1, right, ileft, iright, val);
}

int query(int nod, int left, int right, int ileft, int iright, int qleft, int qright)
{
    if(dir[nod].upper_bound(qright)!=dir[nod].lower_bound(qleft))
        return 1;
    if(ileft<=left && right<=iright)
    {
        if(ind[nod].upper_bound(qright)!=ind[nod].lower_bound(qleft))
            return 1;
        return 0;
    }
    int med=(left+right)/2, sol=0;
    if(ileft<=med)
        sol=max(sol, query(nod*2, left, med, ileft, iright, qleft, qright));
    if(med<iright)
        sol=max(sol, query(nod*2+1, med+1, right, ileft, iright, qleft, qright));
    return sol;
}

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

    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        tata[b]=a;
    }

    for(int i=1; i<=n; ++i)
        if(tata[i]==0)
            df(i);

    while(q--)
    {
        scanf("%d%d%d", &t, &a, &b);
        if(t==2)
            update(1, 1, n, st[a], dr[a], st[b]);
        else
        {
            t=query(1, 1, n, st[a], dr[a], st[b], dr[b]);
            if(t)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}