Cod sursa(job #542406)

Utilizator LgregL Greg Lgreg Data 26 februarie 2011 12:59:41
Problema Gossips Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.13 kb
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
int N,M,Q;
int t[101010];
vector<int> v[101010];
set<int> s[101010];
void dad(int a,int b)
{
    while(a!=0)
    {
    s[a].insert(b);
    a=t[a];
    }
}
void df(int a,int b)
{
    s[a].insert(b);
    vector<int>::iterator p;
    for(p=v[a].begin                                                    ();p!=v[a].end();++p)
        df(*p,b);
}
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<=M;++i)
    {
        scanf("%d%d%d",&tip,&x,&y);
        if(tip==1)
            {
                it=s[x].find(y);
                if(it!=s[x].end())
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        if(tip==2)
        {
            while(y!=0)
            {
            dad(x,y);
            df(x,y);
            y=t[y];
            }
        }
    }
}