Cod sursa(job #1936269)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 22 martie 2017 22:53:02
Problema Gossips Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

#define NMAX 100000

int first[NMAX], last[NMAX];
bool mroot[NMAX];
vector<int> vec[NMAX];
set<int> etree[8 * NMAX];
int N, Q;

void ReadInput() {
    int M;
    scanf("%d%d%d", &N, &M, &Q);
    for (int i = 0; i < M; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        vec[x].push_back(y);
        mroot[y] = true;
    }
}

void DFS(int node) {
    static int etime = 0;
    first[node] = etime++;
    for (const int& son: vec[node])
        DFS(son);
    last[node] = etime++;
}

void AddSegment(int node, int li, int lf, int qi, int qf, int pos) {
    if (qi <= li && lf <= qf) {
        etree[node].insert(pos);
    } else {
        int mid = (li + lf) / 2;
        if (qi <= mid) AddSegment(2 * node, li, mid, qi, qf, pos);
        if (mid < qf) AddSegment(2 * node + 1, mid + 1, lf, qi, qf, pos);
    }
}

bool FindSet(const set<int>& s, int li, int lf) {
    set<int>::iterator it = s.lower_bound(li);
    if (it == s.end()) return false;
    return *it <= lf;
}

bool Query(int node, int li, int lf, int pos, int lpos, int rpos) {
    if (FindSet(etree[node], lpos, rpos)) return true;
    
    if (li != lf) {
        int mid = (li + lf) / 2;
        if (pos <= mid)
            return Query(2 * node, li, mid, pos, lpos, rpos);
        else
            return Query(2 * node + 1, mid + 1, lf, pos, lpos, rpos);
    } 
    return false;
}

void SolveQueries() {
    for (int i = 0; i < N; ++i)
        if (!mroot[i])
            DFS(i);
    while (Q--> 0) {
        int type, x, y;
        scanf("%d%d%d", &type, &x, &y);
        x--; y--;
        if (type == 2) {
            AddSegment(1, 0, 2 * N - 1, first[x], last[x], first[y]);
        } else {
            if (Query(1, 0, 2 * N - 1, first[x], first[y], last[y]))
                puts("YES");
            else 
                puts("NO");
        }
    }
}

int main() {
    freopen("gossips.in", "r", stdin);
    freopen("gossips.out", "w", stdout);
    
    ReadInput();
    SolveQueries();
}