Cod sursa(job #542385)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 26 februarie 2011 12:52:18
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.34 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];
queue <int> q;


int main ()
{
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    int i,nr1,nr2,nr,j;
    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
        {

        }
    }

    return 0;
}

/*#include<algorithm>
using namespace std;
#include<vector>
#include<queue>

#define DIM 100005
#define pb push_back

int n,m,t[DIM],k;
vector <int> lst[DIM],aux,kn[DIM];
queue <int> q;

inline void add (int nr)
{
    int i;
    for(i=0;i<aux.size ();++i)
        kn[nr].pb (aux[i]);
}

int main ()
{
    freopen("gossips.in","r",stdin);
    freopen("gossips.out","w",stdout);
    int i,nr1,nr2,nr,j;
    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)
        {
            aux.clear ();
            for(j=nr2;j!=0;j=t[j])
                aux.pb (j);

            q.push (nr1);
            add (nr1);
            while(!q.empty ())
            {
                nr=q.front ();
                for(j=0;j<lst[nr].size ();++j)
                {
                    add (lst[nr][j]);
                    q.push (lst[nr][j]);
                }
                q.pop ();
            }
            for(j=t[nr1];j!=0;j=t[j])
                add (j);
        }
        else
        {
            gasit=false;
            for(j=0;j<kn[nr1].size ();++j)
                if(kn[nr1][j]==nr2)
                {
                    gasit=true;break;
                }
            if(gasit==true)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }

    return 0;
}
*/