Cod sursa(job #542553)

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

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

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

inline void pars (int &nr)
{
    nr=0;
    while(buff[poz]<'0' || buff[poz]>'9')
        if(++poz==DIMbuff)
            fread(buff,1,DIMbuff,stdin),poz=0;
    while(buff[poz]>='0' && buff[poz]<='9')
    {
        nr=nr*10+buff[poz]-'0';
        if(++poz==DIMbuff)
            fread(buff,1,DIMbuff,stdin),poz=0;
    }
}

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

    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;

    pars(n);
    pars(m);
    pars(k);
    for(i=1;i<=m;++i)
    {
        pars(nr1);
        pars(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)
    {
        pars(nr);
        pars(nr1);
        pars(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;
}