Cod sursa(job #2131834)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 15 februarie 2018 00:01:02
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
#define MAXN 100000

std::vector <int> G[1 + MAXN];
int in[1 + MAXN];
bool seen[1 + MAXN];
int first[1 + MAXN], last[1 + MAXN], ind;
inline void dfs(int node){
    seen[node] = 1;
    first[node] = ++ind;
    for(auto y: G[node]) if(!seen[y]) dfs(y);
    last[node] = ind;
}

std::set <int> S[1 + 4 * MAXN], T[1 + 4 * MAXN];
int left, right, pos, val, ans;
void update(int p, int st, int dr){
    T[p].insert(first[val]);
    if(left <= st && dr <= right);// S[p].insert(first[val]);
    else{
        int m = (st + dr) / 2;
        if(left <= m) update(2 * p, st, m);
        if(m + 1 <= right) update(2 * p + 1, m + 1, dr);
    }
}
void query(int p, int st, int dr){
    if(T[p].size()){
        int a = first[val], b = last[val];
        /*auto it1 = S[p].lower_bound(a), it2 = S[p].upper_bound(b);
        if(it1 != it2) ans = true;*/
        auto it3 = T[p].lower_bound(a), it4 = T[p].upper_bound(b);
        if(it3 != it4) ans = true;
    }
    if(left <= st && dr <= right);
    else{
        int m = (st + dr) / 2;
        if(left <= m) query(2 * p, st, m);
        if(m + 1 <= right) query(2 * p + 1, m + 1, dr);
    }
}

int main(){
    FILE*fi,*fo;
    fi = fopen("gossips.in","r");
    fo = fopen("gossips.out","w");

    int n, m, q;
    fscanf(fi,"%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i++){
        int x, y;
        fscanf(fi,"%d%d", &x, &y);
        G[x].push_back(y);
        in[y]++;
    }
    for(int i = 1; i <= n; i++) if(!in[i]) dfs(i);

    for(int i = 1; i <= q; i++){
        int type, x, y;
        fscanf(fi,"%d%d%d", &type, &x, &y);
        left = first[x];
        right = last[x];
        val = y;
        if(type == 2) update(1, 1, n);
        else{
            ans = false;
            query(1, 1, n);
            if(ans) fprintf(fo,"YES\n");
            else fprintf(fo,"NO\n");
        }
    }

    return 0;
}