Cod sursa(job #542319)

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

using namespace std;

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

const int Dim = 100001;

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

bool Check( int x, int y ) {

    vector <int> :: iterator it;

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

    return 0;
}

void UpdT( int x, int y ) {

    int nod;

    if( x == 0 )
        return;

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

void UpdF( int x, int y ) {

    int nod;
    vector <int> :: iterator it;

    for( nod = y; nod; nod = t[nod] )
        b[x].push_back( nod );
    for( it = v[x].begin(); it != v[x].end(); ++it )
        UpdF( *it, y );
}

int main() {

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

    int x, y, 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 ) {

            if( Check( x, y ) )
                fout << "YES\n";
            else
                fout << "NO\n";
        }
        else {

            UpdT( t[x], y );
            UpdF( x, y );
        }
    }

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

    return 0;
}