Cod sursa(job #2937521)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 10 noiembrie 2022 16:45:55
Problema Gossips Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("gossips.in");
ofstream fout("gossips.out");

const int kN = 1e5;
int timer, tin[1 + kN], tout[1 + kN];
vector<int> g[1 + kN];
bitset<1 + kN> in;

struct ST {
  int n;
  vector<set<int>> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void update(int x, int lx, int rx, int st, int dr, int v) {
    if (st <= lx && rx <= dr) {
      t[x].emplace(v);
      return;
    }
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, v);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, v);
    }
  }

  void update(int u, int v) {
    update(1, 1, n, tin[u], tout[u], tin[v]);
  }

  bool query(int x, int lx, int rx, int st, int dr, int l, int r) {
    auto it = t[x].lower_bound(l);
    if (it != t[x].end() && *it <= r) {
      return true;
    }
    if (st <= lx && rx <= dr) {
      return false;
    }
    int mid = (lx + rx) / 2;
    bool res = false;
    if (st <= mid) {
      res |= query(x * 2, lx, mid, st, dr, l, r);
    }
    if (!res && mid < dr) {
      res |= query(x * 2 + 1, mid + 1, rx, st, dr, l, r);
    }
    return res;
  }

  bool query(int u, int v) {
    return query(1, 1, n, tin[u], tout[u], tin[v], tout[v]);
  }
};

void dfs(int u) {
  tin[u] = ++timer;
  for (int v : g[u]) {
    dfs(v);
  }
  tout[u] = timer;
}

int main() {
  int n, m, q;
  fin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    fin >> u >> v;
    g[u].emplace_back(v);
    in[v] = true;
  }
  for (int v = 1; v <= n; ++v) {
    if (!in[v]) {
      dfs(v);
    }
  }
  ST st(n);
  for (int i = 0; i < q; ++i) {
    int s, x, y;
    fin >> s >> x >> y;
    if (s == 1) {
      if (st.query(x, y)) {
        fout << "YES\n";
      } else {
        fout << "NO\n";
      }
    } else {
      st.update(x, y);
    }
  }
  fin.close();
  fout.close();
  return 0;
}