Cod sursa(job #542435)

Utilizator LgregL Greg Lgreg Data 26 februarie 2011 13:22:59
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.21 kb
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
int N,M,Q;
int t[101010];
vector<int> v[101010],s[101010];
void dad(int a,int b)
{

    while(a!=0)
    {
    s[a].push_back(b);
    a=t[a];
    }
}
void df(int a,int b)
{
   s[a].push_back(b);
    vector<int>::iterator p;
    for(p=v[a].begin();p!=v[a].end();++p)
        df(*p,b);
}
bool find(int a,int b)
{
    vector<int>::iterator p;
    for(p=s[a].begin();p!=s[a].end();++p)
    {
        if(*p==b)
            return 1;
    }
    return 0;
}
int x,y,tip;
int main()
{
freopen("gossips.in","r",stdin);
freopen("gossips.out","w",stdout);
set<int>::iterator it;
scanf("%d%d%d",&N,&M,&Q);
    for(int i=1;i<=M;++i)
    {
        scanf("%d%d",&x,&y);
        t[y]=x;
        v[x].push_back(y);
    }
    for(int i=1;i<=Q;++i)
    {
        scanf("%d%d%d",&tip,&x,&y);
        if(tip==1)
            {

                if(find(x,y))
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        if(tip==2)
        {
            while(y)
            {
            dad(t[x],y);
            df(x,y);
            y=t[y];
            }
        }
    }
}