Cod sursa(job #542315)

Utilizator DraStiKDragos Oprica DraStiK Data 26 februarie 2011 11:31:01
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.41 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back

#define DIM 100005

vector <int> g[DIM],brf[DIM];
int tat[DIM];
int N,M,Q;

void read ()
{
    int i,x,y;

    scanf ("%d%d%d",&N,&M,&Q);
    for (i=1; i<=M; ++i)
    {
        scanf ("%d%d",&x,&y);
        g[x].pb (y);
        tat[y]=x;
    }
}

void df_update (int nod,int who)
{
    vector <int> :: iterator it;
    int newnod;

    for (newnod=who; newnod; newnod=tat[newnod])
        brf[nod].pb (newnod);

    for (it=g[nod].begin (); it!=g[nod].end (); ++it)
        df_update (*it,who);
}

void solve ()
{
    vector <int> :: iterator it;
    int i,tip,x,y,nod,match;

    for (i=1; i<=Q; ++i)
    {
        scanf ("%d%d%d",&tip,&x,&y);
        if (tip==1)
        {
            match=0;
            for (it=brf[x].begin (); it!=brf[x].end (); ++it)
                if (*it==y)
                {
                    printf ("YES\n");
                    match=1;
                }
            if (!match)
                printf ("NO\n");
        }
        else
        {
            df_update (x,y);
            for (x=tat[x]; x; x=tat[x])
                for (nod=y; nod; nod=tat[nod])
                    brf[x].pb (nod);
        }
    }
}

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

    read ();
    solve ();

    return 0;
}