Cod sursa(job #562666)

Utilizator acelasi7Tudor Maxim acelasi7 Data 23 martie 2011 17:36:22
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<vector>
using namespace std;
#define nrn 100001

vector<int> V[nrn];
vector<int>::iterator it;
int t[nrn],g[nrn],nr[nrn],cont,k;

ofstream out("gossips.out");

void numar(int pas)
{
    if(!t[pas] && !nr[pas])
    {
        k=++cont;
        nr[pas]=k;
    }
    else if(nr[pas])
        k=nr[pas];
    else if(t[pas])
    {
        numar(t[pas]);
        nr[pas]=k;
    }
}
void update(int pas,int val)
{
    while(pas)
    {
        V[pas].push_back(val);
        pas=t[pas];
    }
}
void quest(int a,int b)
{
    for(it=V[b].begin();it<V[b].end();++it)
        if(*it==nr[a])
        {
            out<<"YES\n";
            return;
        }
    out<<"NO\n";
}
int main()
{
    int n,m,q,i,x,y,c;
    ifstream in("gossips.in");

    in>>n>>m>>q;
    for(i=1;i<=m;++i)
    {
        in>>x>>y;
        t[y]=x;
    }
    for(i=1;i<=n;++i)
        if(!nr[i])
            numar(i);
    for(i=1;i<=q;++i)
    {
        in>>c>>x>>y;
        switch(c)
        {
            case(1):quest(x,y);break;
            case(2):update(y,nr[x]);break;
        }
    }
    return 0;
}