Cod sursa(job #542436)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 26 februarie 2011 13:25:14
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.6 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;
    if(x==y)
        return 1;

    for(i=x;i!=0;i=t2[i])
        if(i==y)
            return 1;
    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(check(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;
}