IOI '18 - Werewolf (49pts)

#include "werewolf.h"
#include <queue>
#include <algorithm>

using namespace std;

// SUBTASK 3
const int MAX_N = 2e5+1, LG = 19;
int mx[LG][MAX_N], mn[LG][MAX_N];
int getMN(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return min(mn[i][l], mn[i][r-p2+1]);
}
int getMX(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return max(mx[i][l], mx[i][r-p2+1]);
}

vector<int> check_validity(int N, vector<int> X,  vector<int> Y,
  vector<int> S, vector<int> E,
  vector<int> L, vector<int> R) {
  int M = X.size(), Q = S.size();
  vector<int> A(Q);

  if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
    vector<vector<int>> g(N);
    for (int i = 0; i < M; ++i) {
      g[X[i]].push_back(Y[i]);
      g[Y[i]].push_back(X[i]);
    }
    for (int qq = 0; qq < Q; ++qq) {
      int s = S[qq], e = E[qq], l = L[qq], r = R[qq];

      // bfs from start as human
      vector<bool> canHuman(N);
      queue<int> q;
      q.push(s), canHuman[s] = true;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x]) {
          if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
        }
      }

      vector<bool> canWolf(N);
      q.push(e), canWolf[e] = true;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x]) {
          if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
        }
      }

      for (int i = 0; i < N; ++i) {
        if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
      }
    }
  } else { // subtask 3
    // find order for nodes
    vector<vector<int>> g(N);
    for (int i = 0; i < M; ++i) {
      g[X[i]].push_back(Y[i]);
      g[Y[i]].push_back(X[i]);
    }

    int endPoint = 0;
    for (int i = 0; i < N; ++i) {
      if (g[i].size() == 1) {
        endPoint = i;
        break;
      }
    }

    // move from endpoint and mark nodes
    vector<int> id(N);
    id[0] = endPoint;
    for (int i = 1, cur = g[id[0]][0]; i < N; ++i) {
      id[i] = cur;
      cur = g[cur][0] + g[cur][1] - id[i-1];
    }

    vector<int> linePos(N);
    for (int i = 0; i < N; ++i) linePos[id[i]] = i;

    // store range maximums and minimums with sparse table
    for (int i = 0; i < N; ++i) mx[0][i] = mn[0][i] = id[i];
    for (int i = 1, p2 = 1; i < LG; ++i, p2<<=1) {
      for (int j = 0; j < N; ++j) {
        mx[i][j] = max(mx[i-1][j], mx[i-1][j+p2]);
        mn[i][j] = min(mn[i-1][j], mn[i-1][j+p2]);
      }
    }

    for (int qq = 0; qq < Q; ++qq) {
      int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      s = linePos[s], e = linePos[e];

      if (s < e) {
        // find last H (only allowing humans) after start
        //  (last one > R)
        int left = s-1, right = e; // there is an H on or after left, not right
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMX(mid, e) > r) left = mid;
          else right = mid;
        }
        int lastH = left;

        // find first W (only allowing werewolves) after start
        //  (first one < L)
        left = s, right = e+1; // there is W on or before right, not left
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMN(s, mid) < l) right = mid;
          else left = mid;
        }
        int firstW = right;

        if (lastH+1 < firstW) A[qq] = 1;
      } else {
        // find last W (only allowing werewolves) after end
        //  (last one < L)
        int left = e-1, right = s; // there is a W on or after left, not right
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMN(mid, s) < l) left = mid;
          else right = mid;
        }
        int lastW = left;

        // find first H (only allowing humans) after end
        //  (first one > R)
        left = e, right = s+1; // there is an H on or before right, not left
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMX(e, mid) > r) right = mid;
          else left = mid;
        }
        int firstH = right;

        if (lastW+1 < firstH) A[qq] = 1;
      }
    }
  }

  return A;
}