Cod sursa(job #2714977)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 2 martie 2021 19:49:57
Problema Gossips Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct segment_tree{
    set<int> s1; /// valorile astea se afla in unele elemente din interval
    set<int> s2; /// valorile astea se afla in toate elementele din interval
} aint[DIM*4];

vector <int> L[DIM];
int first[DIM],last[DIM],viz[DIM],g[DIM];
int n,m,q,x,y,tip,ok,idx,i;

void dfs (int nod){
    viz[nod] = 1;
    first[nod] = ++idx;
    for (auto vecin : L[nod]){
        if (!viz[vecin])
            dfs (vecin);
    }
    last[nod] = idx;
}

void update (int nod, int st, int dr, int x, int y, int val){
    aint[nod].s1.insert(val);
    if (x <= st && dr <= y){
        aint[nod].s2.insert(val);
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);
}

void query (int nod, int st, int dr, int x, int y, int Left, int Right){

    /// query in setul2, pt ca stiu ca setul asta se afla in nodurile din tot subarborele
    set<int> :: iterator it = aint[nod].s2.lower_bound(Left);
    if (it != aint[nod].s2.end() && *it <= Right)
        ok = 1;

    if (x <= st && dr <= y){
        /// acum ma intereseaza doar sa fie undeva in subarbore
        it = aint[nod].s1.lower_bound(Left);
        if (it != aint[nod].s1.end() && *it <= Right)
            ok = 1;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y,Left,Right);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y,Left,Right);
}

int main (){

    ifstream cin ("gossips.in");
    ofstream cout ("gossips.out");

    cin>>n>>m>>q;
    for (i=1;i<=m;i++){
        cin>>x>>y;
        L[x].push_back(y);
        g[y]++;
    }

    for (i=1;i<=n;i++)
        if (!g[i])
            dfs (i);

    for (;q--;){
        cin>>tip>>x>>y;
        if (tip == 1){
            ok = 0;
            query (1,1,n,first[x],last[x],first[y],last[y]);

            if (ok)
                cout<<"YES\n";
            else cout<<"NO\n";
        } else {
            update (1,1,n,first[x],last[x],first[y]);
        }
    }


    return 0;
}