Cod sursa(job #562138)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 22 martie 2011 13:46:46
Problema Gossips Scor 100
Compilator cpp Status done
Runda againrmms Marime 1.78 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define nmax 100010
 
int n, m, q, a[nmax], b[nmax], h, val, st, dr, a1, b1, ok;
set <int> arb[4*nmax], arb2[4*nmax];
vector <int> g[nmax];
char u[nmax];
 
void df(int nod)
{
    int i;
    a[nod]=++h;
    for (i=0; i<g[nod].size(); i++)
        if (!a[g[nod][i]]) df(g[nod][i]);
    b[nod]=h;
}
 
void update(int nod, int l, int r)
{
    arb2[nod].insert(val);
    if (st<=l && r<=dr) arb[nod].insert(val); else
    {
        int m=(l+r)/2;
       if (st<=m) update(2*nod, l, m);
        if (m<dr) update(2*nod+1, m+1, r);
    }
}
 
void query(int nod, int l, int r)
{
    if (ok) return;
    set <int>:: iterator it=arb[nod].lower_bound(a1);
    if (it!=arb[nod].end() && (*it)<=b1) ok=1;
    if (st<=l && r<=dr)
    {
        it=arb2[nod].lower_bound(a1);
        if (it!=arb2[nod].end() && (*it)<=b1) ok=1;
    } else
    {
        int m=(l+r)/2;
        if (st<=m) query(2*nod, l, m);
        if (m<dr) query(2*nod+1, m+1, r);
    }
}
 
int main()
{
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    scanf("%d %d %d",&n, &m, &q);
    int i, x, y, c;
    for (i=1; i<=m; i++)
    {
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        u[y]=1;
    }
    for (i=1; i<=n; i++)
        if (!u[i])
            df(i);
    while (q--)
    {
        scanf("%d %d %d",&c, &x, &y);
        if (c==2)
        {
            st=a[x];
            dr=b[x];
            val=a[y];
            update(1, 1, n);
        } else
        {
            st=a[x];
            dr=b[x];
            a1=a[y];
            b1=b[y];
            ok=0;
			   query(1, 1, n);
            if (ok) printf("YES\n"); else printf("NO\n");
        }
    }
}