Cod sursa(job #542340)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 26 februarie 2011 12:00:32
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.67 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

const char Input[] = "gossips.in";
const char Output[] = "gossips.out";

const int Dim = 100001;

bool ok;
int N, M, Q;
int t[Dim];
vector <int> b[Dim], v[Dim];

void CheckT( int x, int y ) {

    vector <int> :: iterator it;

    if( x == 0 || ok == true )
        return;

    for( it = b[x].begin(); it != b[x].end(); ++it )
        if( *it == y ) {

            ok = true;
            return;
        }

    CheckT( t[x], y );
}

void CheckF( int x, int y ) {

    vector <int> :: iterator it;

    if( ok == true )
        return;

    for( it = b[x].begin(); it != b[x].end(); ++it )
        if( *it == y ) {

            ok = true;
            return;
        }

    for( it = v[x].begin(); it != v[x].end(); ++it )
        CheckF( *it, y );
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int x, y, nod, tip;

    fin >> N >> M >> Q;
    while( M-- ) {

        fin >> x >> y;
        v[x].push_back( y );
        t[y] = x;
    }
    while( Q-- ) {

        fin >> tip >> x >> y;
        if( tip == 1 ) {

            ok = false;
            CheckF( x, y );
            if( ok == true )
                fout << "YES\n";
            else {

                CheckT( t[x], y );
                if( ok == true )
                    fout << "YES\n";
                else
                    fout << "NO\n";
            }
        }
        else {

            for( nod = y; nod; nod = t[nod] )
                b[x].push_back( nod );
        }
    }

    fin.close();
    fout.close();

    return 0;
}