Cod sursa(job #542482)

Utilizator gorgovanAurelian Namascu gorgovan Data 26 februarie 2011 14:10:14
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.77 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],ok;

void dfs(int x,int y)
{
    if(C[x][y]==1)
      ok=1;
    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;

    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;
    int aux;
    for(i=1;i<=Q;i++)
    {
        fin>>op>>x>>y;
        if(op==2)
         {

             C[x][y]=1;
             while(T2[y])
             {
                 y=T2[y];

                 C[x][y]=1;

             }
         }
         else
         {
             ok=0;
             aux=x;
             if(C[aux][y])
               ok=1;
             while(T2[aux])
             {
                 aux=T2[aux];

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

int main()
{
    cit();



    fout.close();
}