Cod sursa(job #542404)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 26 februarie 2011 12:59:05
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 3.03 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <iostream>
#define pb push_back

using namespace std;

int N, M, Q;
const int nmax = 100010;
int T[nmax], which[nmax];
vector<int> G[nmax];
vector<int> knows[nmax];
vector<int> about[nmax];
vector<int>::iterator it;
stack<int> S;

void read()
{

    freopen ("gossips.in","r",stdin);
    freopen ("gossips.out","w",stdout);
    scanf("%d %d %d",&N,&M,&Q);
    int a, b, i;
    for(i = 1; i <= M; i++)
    {
        scanf("%d %d",&a,&b);
        G[a].pb(b);
        T[b] = a;
    }
}

int mark;

void marque()
{
    int i, x;
    for(i = 1; i <= N; i++)
        if(!T[i])
        {
            S.push(i);
            which[i] = ++mark;
            while(!S.empty())
            {
                x = S.top();
                S.pop();
                for(it = G[x].begin(); it < G[x].end(); it++)
                {
                    which[*it] = mark;
                    S.push(*it);
                }
            }
        }
}

bool exist(int grup, int y)
{
    if(knows[grup].size() < about[y].size())
        for(it = knows[grup].begin(); it < knows[grup].end(); it++)
        {
            if(*it == y)
                return true;
        }
    else
    {
        for(it = about[y].begin(); it < about[y].end(); it++)
            if(*it == grup)
                return true;
    }
    return false;
}

int main()
{
    read();
    //marque();
    int i, x, y, op, grup, temp;
    bool tre;
    for(i = 1; i <= Q; i++)
    {
        scanf("%d %d %d",&op,&x,&y);
        if(op == 1)
        {
            //grup = which[x];
            if(exist(x, y))
                printf("YES\n");
            else printf("NO\n");
        }
        else
        {
            //grup = which[x];
            if(!exist(x,y))
            {
                S.push(x);
                mark = 0;
                while(!S.empty())
                {
                    temp = S.top();
                    S.pop();
                    tre = true;
                    for(it = G[temp].begin(); it < G[temp].end(); it++)
                    {
                        tre = false;
                        S.push(*it);
                    }
                    if(tre)
                        which[++mark] = temp;
                }
            }

            do
            {
                for(grup = 1; grup <= mark; grup++)
                    if(!exist(which[grup],y))
                    {
                        temp = which[grup];
                        while(temp)
                        {
                            if(!exist(temp, y))
                            {
                                knows[temp].pb(y);
                                about[y].pb(temp);
                            }
                            else break;
                            temp = T[temp];
                        }
                    }
                y = T[y];
            } while(y);
        }
    }

    return 0;
}