Cod sursa(job #2030462)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 1 octombrie 2017 17:30:11
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <cctype>
#include <vector>
#include <set>

#define BUF_SIZE 1 << 17

int pos = BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin = fopen("gossips.in", "r"), *fout = fopen("gossips.out", "w");

inline char nextch() {
    if (pos == BUF_SIZE) fread(buf, 1, BUF_SIZE, fin), pos = 0;
    return buf[pos++];
}

inline int read() {
    char ch;
    while (!isdigit(ch = nextch()));
    int x = ch - '0';
    while (isdigit(ch = nextch())) x = 10 * x + ch - '0';
    return x;
}

#define MAXN 100000

#define pet std::set < int, cmp >

int o;
char ans[4 * MAXN];

std::vector <int> g[MAXN + 1];
bool t[MAXN + 1];
int k, l[MAXN + 1], r[MAXN + 1];

struct cmp {
    inline bool operator() (const int &a, const int &b) const {
        return l[a] < l[b];
    }
};

pet aint[2 * MAXN];
pet::iterator it;

int n, poz, val;
bool rez;

inline void baga(pet &s) {
    it = s.upper_bound(val);
    if (it != s.begin()) {
        it--;
        if (l[val] < r[*it])
            return ;
        it++;
    }
    while (it != s.end() && l[*it] < r[val]) {
        s.erase(it);
        it = s.lower_bound(val);
    }
    s.insert(val);
}

inline void update() {
    poz = l[poz] + n - 1;
    while (poz) {
        baga(aint[poz]);
        poz /= 2;
    }
}

inline void check(pet s) {
    it = s.lower_bound(val);
    if (it != s.end() && l[*it] < r[val])
        rez = 1;
    else if (it != s.begin()) {
        it--;
        rez = bool(l[val] < r[*it]);
    }
}

inline void query() {
    int left = l[poz] + n - 1, right = r[poz] + n - 2;
    while (left <= right && !rez) {
        check(aint[left]);
        if (!rez && left != right)
            check(aint[right]);
        left = (left + 1) / 2;
        right = (right - 1) / 2;
    }
}

void dfs(int x) {
    l[x] = k++;
    for (auto &y : g[x])
        dfs(y);
    r[x] = k;
}

int main() {
    n = read();
    int m = read();
    int q = read();

    for (int i = 0; i < m; i++) {
        int x = read();
        int y = read();

        t[y] = 1;
        g[x].push_back(y);
    }

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

    for (int i = 0; i < q; i++) {
        int s = read();
        val = read();
        poz = read();

        if (s == 2) update();
        else{
            rez = 0;
            query();
            if (rez) {
                ans[o++] = 'Y';
                ans[o++] = 'E';
                ans[o++] = 'S';
            } else {
                ans[o++] = 'N';
                ans[o++] = 'O';
            }
            ans[o++] = '\n';
        }
    }

    fwrite(ans, 1, o, fout);
    fclose(fin);
    fclose(fout);
    return 0;
}