Cod sursa(job #1759792)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 septembrie 2016 20:37:00
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <queue>
#include <cstring>
#include <set>

using namespace std;

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

const int MAXN = 100000;

bool notRoot[1 + MAXN], ok;
int first[1 + MAXN], last[1 + MAXN];
vector<int> g[1 + MAXN];
int pointer = 0;

void DFS(int node) {
    pointer++;
    first[node] = pointer;
    for (auto &son : g[node])
        DFS(son);
    pointer++;
    last[node] = pointer;
}

set<int> tree[1 + 8 * MAXN], lazy[1 + 8 * MAXN];

void Update(int node, int left, int right, int a, int b, int value) {
    tree[node].insert(value);
    if (a <= left && right <= b) {
        lazy[node].insert(value);
        return;
    }
    int middle = (left + right) / 2;
    if (a <= middle)
        Update(2 * node, left, middle, a, b, value);
    if (middle + 1 <= b)
        Update(2 * node + 1, middle + 1, right, a, b, value);
}

bool Search(int left, int right, set<int> &Set) {
    auto it = Set.lower_bound(left);
    if (it == Set.end() || *it > right)
        return false;
    return true;
}

void Query(int node, int left, int right, int x, int y, int a, int b) {
    if (ok)
        return;
    if (Search(a, b, lazy[node])) {
        ok = true;
        return;
    }
    if (x <= left && right <= y) {
        if (Search(a, b, tree[node]))
            ok = true;
        return;
    }
    int middle = (left + right) / 2;
    if (x <= middle)
        Query(2 * node, left, middle, x, y, a, b);
    if (middle + 1 <= y)
        Query(2 * node + 1, middle + 1, right, x, y, a, b);
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        notRoot[b] = true;
    }
    for (int i = 1; i <= n; i++)
        if (!notRoot[i])
            DFS(i);
    for (int i = 1; i <= q; i++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 2)
            Update(1, 1, pointer, first[a], last[a], first[b]);
        else {
            ok = false;
            Query(1, 1, pointer, first[a], last[a], first[b], last[b]);
            if (ok)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    return 0;
}