Cod sursa(job #542427)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 26 februarie 2011 13:18:27
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.02 kb
#include<algorithm>
using namespace std;
#include<vector>
#include<queue>

#define DIM 100005
#define mp make_pair
#define fs first
#define sc second
#define pb push_back

int n,m,t[DIM],t2[DIM],k;
vector <int> lst[DIM];
vector <pair<int,int> > kn[DIM];

inline bool check (int x,int y)
{
    int i;
    for(i=x;i!=0;i=t2[i])
        if(i==y)
            return 1;
    return 0;
}

inline bool fiu (int x,int y)
{
    queue <int> q;
    int nr,i;

    if(x==y)
        return 1;

    q.push (y);
    while(!q.empty ())
    {
        nr=q.front ();
        for(i=0;i<lst[nr].size ();++i)
            if(lst[nr][i]==x)
            {
                while(!q.empty ())
                    q.pop ();
                return 1;
            }
            else
                q.push(lst[nr][i]);
        q.pop ();
    }
    return 0;
}

int main ()
{
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    int i,nr1,nr2,nr,j,rad;
    bool gasit;

    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&nr1,&nr2);
        t[nr2]=nr1;
        t2[nr2]=nr1;
        lst[nr1].pb (nr2);
    }
    for(i=1;i<=n;++i)
    {
        for(j=i;t[j]!=0;j=t[j]);
        t[i]=j;
    }


    for(i=1;i<=k;++i)
    {
        scanf("%d%d%d",&nr,&nr1,&nr2);
        if(nr==2)
        {
            kn[t[nr2]].pb (mp (nr1,nr2));
        }
        else
        {
            rad=t[nr2];
            gasit=false;
            for(j=0;j<kn[rad].size ();++j)
                if(fiu(kn[rad][j].sc,nr2))
                {
                    if(check(nr1,kn[rad][j].fs))
                    {
                        gasit=true;break;
                    }
                    if(check(kn[rad][j].fs,nr1))
                    {
                        gasit=true;break;
                    }
                }
            if(gasit==true)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}