Cod sursa(job #2522547)

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

FILE * fin = fopen("gossips.in","r");
FILE *  fout = fopen("gossips.out","w");

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(){

    fscanf( fin, "%d%d%d", &N, &M, &Q );
    for( int i = 1; i <= M; i++ ){
        int x, y; fscanf( fin, "%d%d", &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; fscanf( fin, "%d%d%d", &op, &x, &y );
        if( op == 2 ){
            update( 1, 1, nr, first[x], last[x], first[y] );
        }else{
            fprintf( fout, ( ( query(1, 1, nr, first[x], last[x], first[y], last[y]) == true ) ? "YES\n" : "NO\n" ) );
        }
    }

    return 0;
}