Cod sursa(job #542376)

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

using namespace std;

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

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

const int Dim = 100001;
const int MaxL = 10001;

bool ok;
char s[MaxL];
int N, M, Q, L;
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 );
}

inline void Read( int &x ) {

    while( !isdigit( s[L] ) )
        if( ++L == MaxL ) {

            fin.read( s, MaxL );
            L = 0;
        }
    for( x = 0; isdigit( s[L] ); ) {

        x = x * 10 + s[L] - '0';
        if( ++L == MaxL ) {

            fin.read( s, MaxL );
            L = 0;
        }
    }
}

int main() {

    int x, y, nod, tip;

    Read( N ); //fin >> N;
    Read( M ); //fin >> M;
    Read( Q ); //fin >> Q;

    while( M-- ) {

        Read( x ); //fin >> x;
        Read( y ); //fin >> y;

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

        Read( tip ); //fin >> tip;
        Read( x ); //fin >> x;
        Read( y ); //fin >> 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;
}