Cod sursa(job #2522543)

Utilizator robx12lnLinca Robert robx12ln Data 12 ianuarie 2020 17:42:27
Problema Gossips Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>
#define Nst ((nod<<1)^0)
#define Ndr ((nod<<1)|1)
#define mid ((st + dr)>>1)
using namespace std;

ifstream fin("gossips.in");
ofstream  fout("gossips.out");

const int DIM = 1e5 + 2;

int N, M, Q, grad[DIM], first[DIM], last[DIM], nr;
vector<int> edge[DIM];

void dfs( int nod ){
    first[nod] = ++nr;
    for( int i = 0; i < edge[nod].size(); i++ )
        dfs( edge[nod][i] );
    last[nod] = nr;
}

struct aint{
    set<int> S[2]; /// S0 - upd din el se aplica pt tot subarborele, S1 - upd din el sunt venite din subarbore (adica pt lant)
} A[4 * DIM];

void update( int nod, int st, int dr, int a, int b, int x ){
    A[nod].S[1].insert(x);
    if( a <= st && dr <= b ) {
        A[nod].S[0].insert(x);
        return;
    }
    if( a <= mid )
        update( Nst, st, mid + 0, a, b, x );
    if( b > mid )
        update( Ndr, mid + 1, dr, a, b, x );
    return;
}

set<int>::iterator it;
inline bool check( int nod, int t, int x, int y ){
    it = A[nod].S[t].lower_bound( x );
    if( it != A[nod].S[t].end() && (*it) <= y )
        return true;
    return false;
}

bool query( int nod, int st, int dr, int a, int b, int x, int y ){
    if( check( nod, 0, x, y ) == true )
        return true;
    if( a <= st && dr <= b )
        return check( nod, 1, x, y );
    if( a <= mid && query( Nst, st,mid + 0, a, b, x, y ) )
        return true;
    if( b > mid && query( Ndr, mid + 1, dr, a, b, x, y ) )
        return true;
    return false;
}

int main(){

    fin >> N >> M >>  Q;
    for( int i = 1; i <= M; i++ ){
        int x, y; fin >> x >> y;
        edge[x].push_back( y );
        grad[y]++;
    }

    nr = 0;
    for( int i = 1; i <= N; i++ ){
        if( grad[i] == 0 )
            dfs( i );
    }

    for( int i = 1; i <= Q; i++ ){
        int op, x, y; fin >> op >> x >> y;
        if( op == 2 ){
            update( 1, 1, nr, first[x], last[x], first[y] );
        }else{
            fout << ( ( query(1, 1, nr, first[x], last[x], first[y], last[y]) == true ) ? "YES\n" : "NO\n" );
        }
    }

    return 0;
}