Cod sursa(job #542508)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 26 februarie 2011 14:25:05
Problema Gossips Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.81 kb
#include<stdio.h>
#include<vector>
using namespace std;

#define pb push_back
#define NMAX 100006

int n,m,k,nr;
int tata[NMAX];
int trans[NMAX];
int last[NMAX];
vector<int> vf[NMAX];
vector<int> muc[NMAX];


void dfs_time(int nod)
{
    int i,lim,vec;
    trans[nod]=++nr;
    lim=vf[nod].size();
    for(i=0;i<lim;i++)
    {
        vec=vf[nod][i];
        if(!trans[vec])
            dfs_time(vec);
    }
    last[nod]=nr;
}

int dfs_tata(int nod,int p1,int p2)
{
    if(!nod)
        return 0;
    int i,lim=muc[nod].size();
    for(i=lim-1;i>=0;i--)
        if(p1<=muc[nod][i] && muc[nod][i]<=p2)
            return 1;
    return dfs_tata(tata[nod],p1,p2);
}

int dfs_fiu(int nod,int p1,int p2)
{
    int i,lim=muc[nod].size();
    for(i=lim-1;i>=0;i--)
        if(p1<=muc[nod][i] && muc[nod][i]<=p2)
            return 1;
    int r;
    lim=vf[nod].size();
    for(i=lim-1;i>=0;i--)
    {
        r=dfs_fiu(vf[nod][i],p1,p2);
        if(r)
            return 1;
    }
    return 0;
}

int main ()
{
    int i,a,b,r,tip;
    
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        tata[b]=a;
        vf[a].pb(b);
    }
    for(i=1;i<=n;i++)
       if(!tata[i])
           dfs_time(i);
    for(i=1;i<=k;i++)
    {
        scanf("%d%d%d",&tip,&a,&b);
        if(tip==2)
        {
            muc[a].pb(trans[b]);
            continue;
        }
        r=dfs_tata(a,trans[b],last[b]);
        if(r)
            printf("YES\n");
        else
        {
            r=dfs_fiu(a,trans[b],last[b]);
            if(r)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}