Cod sursa(job #542341)

Utilizator DraStiKDragos Oprica DraStiK Data 26 februarie 2011 12:02:02
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.48 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_tat (int nod,int start)
{
    int who;

    if (!nod)
        return ;

    df_tat (tat[nod],start);
    for (who=start; who; who=tat[who])
        brf[nod].pb (who);
}

void df_fii (int nod,int start)
{
    vector <int> :: iterator it;
    int who;

    for (it=g[nod].begin (); it!=g[nod].end (); ++it)
        df_fii (*it,start);
    for (who=start; who; who=tat[who])
        brf[nod].pb (who);
}

inline int knows (int nod,int who)
{
    vector <int> :: iterator it;

    for (it=brf[nod].begin (); it!=brf[nod].end (); ++it)
        if (*it==who)
            return 1;

    return 0;
}

void solve ()
{
    int i,tip,x,y;

    for (i=1; i<=Q; ++i)
    {
        scanf ("%d%d%d",&tip,&x,&y);
        if (tip==1)
        {
            if (knows (x,y))
                printf ("YES\n");
            else
                printf ("NO\n");
        }
        else
        {
            df_tat (tat[x],y);
            df_fii (x,y);
        }
    }
}

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

    read ();
    solve ();

    return 0;
}