Cod sursa(job #542417)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 26 februarie 2011 13:09:52
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.98 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],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=t[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;
        lst[nr1].pb (nr2);
    }
    for(i=1;i<=k;++i)
    {
        scanf("%d%d%d",&nr,&nr1,&nr2);
        if(nr==2)
        {
            for(j=nr2;t[j]!=0;j=t[j]);
                kn[j].pb (mp (nr1,nr2));
        }
        else
        {
            for(j=nr2;t[j]!=0;j=t[j]);
            rad=j;
            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;
}