Cod sursa(job #987048)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 august 2013 22:58:47
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <cstdio>
#include <cassert>

#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int NIL = -1;

class SegmentTree {
  public:
    SegmentTree(const int length) {
        for (size = 1; size < 2 * length; size *= 2);
        contains = contained = vector< set<int> >(2 * size + 1, set<int>());
    }

    void Insert(const int from, const int to, const int value) {
        Insert(1, 0, size - 1, from, to, value);
    }

    bool Find(const int from, const int to, const int begin, const int end) const {
        return Find(1, 0, size - 1, from, to, begin, end);
    }

  private:
    int size;
    vector< set<int> > contains, contained;

    void Insert(const int node, const int left, const int right, const int from, const int to, const int value) {
        int middle = (left + right) / 2;
        contains[node].insert(value);
        if (from <= left && right <= to) {
            contained[node].insert(value);
            return;
        }
        if (from <= middle)
            Insert(2 * node, left, middle, from, to, value);
        if (middle < to)
            Insert(2 * node + 1, middle + 1, right, from, to, value);
    }

    bool Find(const int node, const int left, const int right, const int from, const int to, const int begin, const int end) const {
        int middle = (left + right) / 2;
        auto v = contained[node].lower_bound(begin);
        if (v != contained[node].end() && *v <= end)
            return true;
        v = contains[node].lower_bound(begin);
        if (v == contains[node].end() || end < *v)
            return false;
        if (from <= left && right <= to)
            return (*v <= end);
        if (from <= middle)
            if (Find(2 * node, left, middle, from, to, begin, end))
                return true;
        if (middle < to)
            if (Find(2 * node + 1, middle + 1, right, from, to, begin, end))
                return true;
        return false;
    }
};

vector< vector<int> > Tree;
int V, Q, Euler;
vector<int> Father, Begin, End;

void DFS(const int x) {
    Begin[x] = Euler++;
    for (const auto &y: Tree[x])
        DFS(y);
    End[x] = Euler - 1;
}

void Solve() {
    for (int x = 0; x < V; ++x)
        if (Father[x] == NIL)
            DFS(x);
    SegmentTree segmentTree(Euler);
    for (; Q > 0; --Q) {
        int type, x, y;
        assert(scanf("%d %d %d", &type, &x, &y) == 3);
        --x;
        --y;
        if (type == 1) {
            if (segmentTree.Find(Begin[x], End[x], Begin[y], End[y]))
                printf("YES\n");
            else
                printf("NO\n");
        } else if (type == 2) {
            segmentTree.Insert(Begin[x], End[x], Begin[y]);
        }
    }
}

void Read() {
    int e;
    assert(scanf("%d %d %d", &V, &e, &Q) == 3);
    Tree = vector< vector<int> >(V, vector<int>());
    Father = vector<int>(V, NIL);
    Begin = End = vector<int>(V, 0);
    for (; e > 0; --e) {
        int x, y;
        assert(scanf("%d %d", &x, &y) == 2);
        --x;
        --y;
        Tree[x].push_back(y);
        Father[y] = x;
    }
}

int main() {
    assert(freopen("gossips.in", "r", stdin));
    assert(freopen("gossips.out", "w", stdout));
    Read();
    Solve();
    return 0;
}