Cod sursa(job #542450)

Utilizator gorgovanAurelian Namascu gorgovan Data 26 februarie 2011 13:40:40
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.46 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<bitset>
#define pb push_back
#define nmax 10005
ofstream fout("gossips.out");
bitset<nmax> C[nmax];
vector<int> G[nmax],GT[nmax];
int N,M,Q;

int T[nmax],T2[nmax];

void dfs(int x,int y)
{
    T[x]=y;
    vector<int>::iterator it;
    for(it=G[x].begin();it<G[x].end();it++)
    {
        dfs(*it,y);
    }
}

void prelucrare()
{int i;
    for(i=1;i<=N;i++)
    {
        if(GT[i].size()==0)
        {

            dfs(i,i);
        }
    }
}

void cit()
{

    ifstream fin("gossips.in");
    int i,x,y,op;
    fin>>N>>M>>Q;
    if(N>10000)
       for(;;);
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].pb(y);
        T[y]=x;
        T2[y]=x;
        GT[y].pb(x);
    }
    prelucrare();
    /*for(i=1;i<=N;i++)
      cout<<T[i]<<" ";
     cout<<"\n";*/
    vector<int>::iterator it;
    for(i=1;i<=Q;i++)
    {
        fin>>op>>x>>y;
        if(op==2)
         {
             C[T[x]][y]=1;
             while(T2[y])
             {
                 y=T2[y];

                 C[T[x]][y]=1;

             }
         }
         else
         {
             if(C[T[x]][y]==1)
             {
                 fout<<"YES\n";
             }
             else
             {
                 fout<<"NO\n";
             }
         }
    }
    fin.close();
}

int main()
{
    cit();



    fout.close();
}