제출 #222771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222771		rama_pang	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1333 ms	127256 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

// Disjoint Set
vector<int> disj;
int Find(int x) {
  return disj[x] == x ? x : disj[x] = Find(disj[x]);
}

class BIT {
 private:
  int sz;
  vector<int> tree;
  
  void Update_(int p, int x) {
    for (int i = p + 1; i <= sz; i += (i & -i)) {
      tree[i - 1] += x;
    }
  }

  int Query_(int p) {
    int res = 0;
    for (int i = p + 1; i > 0; i -= (i & -i)) {
      res += tree[i - 1];
    }
    return res;
  }

 public:
  BIT() {}
  BIT(int n) : sz(n) { tree.assign(sz, 0); }

  void Update(int p, int x) {
    return Update_(p, x);
  }

  int Query(int L, int R) {
    return Query_(R) - Query_(L - 1);
  }
};

// Line Sweep
struct Event {
  int type; // 0 (point), 1 (query end), -1 (query start)
  int lo, hi;
  int id;
  Event() {}
  Event(int t, int l, int h, int i) : type(t), lo(l), hi(h), id(i) {}
  bool operator < (const Event &o) const { return type < o.type; }
};

vector<vector<Event>> events;

void AddPoint(int x, int y) {
  events[x].emplace_back(0, y, y, -1);
}

void AddQuery(int x_1, int x_2, int y_1, int y_2) {
  static int id_ = 0;
  events[x_1].emplace_back(-1, y_1, y_2, id_);
  events[x_2].emplace_back(+1, y_1, y_2, id_);
  id_++;
}

void LineSweep(int n, vector<int> &InsideRectangle) {
  BIT tree(n);
  for (int x = 0; x < n; x++) {
    sort(begin(events[x]), end(events[x]));
    for (auto e : events[x]) {
      if (e.type == 0) { // Add Point
        tree.Update(e.lo, +1);
      } else { // Process Query
        InsideRectangle[e.id] += e.type * tree.Query(e.lo, e.hi);
      }
    }
  }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, 
                           vector<int> E, vector<int> L, vector<int> R) {
  
  disj.resize(N), events.resize(2 * N);
  vector<vector<int>> adj(N);
  for (int i = 0; i < (int) X.size(); i++) {
    adj[X[i]].emplace_back(Y[i]);
    adj[Y[i]].emplace_back(X[i]);
  }

  vector<int> LineL, LineR;
  vector<vector<int>> AncL(N, vector<int>(20, -1)), AncR(N, vector<int>(20, -1));

  function<void(int, vector<vector<int>>&, vector<vector<int>>&, vector<int>&)> dfs = [&](
      int n, vector<vector<int>> &adjList, vector<vector<int>> &anc, vector<int> &v) {
    v.emplace_back(n);
    for (int j = 1; j < 20; j++) {
      if (anc[n][j - 1] != -1) {
        anc[n][j] = anc[anc[n][j - 1]][j - 1];
      }
    }
    for (auto i : adjList[n]) {
      anc[i][0] = n;
      dfs(i, adjList, anc, v);
    }
    v.emplace_back(n);
  };

  { // Created rooted tree for L (low-population restricted)
    iota(begin(disj), end(disj), 0);
    vector<vector<int>> tree(N);
    for (int u = N - 1; u >= 0; u--) {
      for (auto v : adj[u]) {
        if (v < u) continue;
        if (u == Find(v)) continue;
        tree[u].emplace_back(Find(v));
        disj[Find(v)] = u;
      }
    }
    AncL[0][0] = -1;
    dfs(0, tree, AncL, LineL);
  }

  { // Created rooted tree for R (high-population restricted)
    iota(begin(disj), end(disj), 0);
    vector<vector<int>> tree(N);
    for (int u = 0; u < N; u++) {
      for (auto v : adj[u]) {
        if (v > u) continue;
        if (u == Find(v)) continue;
        tree[u].emplace_back(Find(v));
        disj[Find(v)] = u;
      }
    }
    AncR[N - 1][0] = -1;
    dfs(N - 1, tree, AncR, LineR);
  }

  vector<pair<int, int>> posL(N, {-1, -1}), posR(N, {-1, -1});
  for (int i = 0; i < 2 * N; i++) {
    if (posL[LineL[i]].first == -1) {
      posL[LineL[i]].first = i;
    } else {
      posL[LineL[i]].second = i;
    }
    if (posR[LineR[i]].first == -1) {
      posR[LineR[i]].first = i;
    } else {
      posR[LineR[i]].second = i;
    }
  }

  for (int i = 0; i < N; i++) {
    AddPoint(posL[i].first, posR[i].first);
  }
  
  int Q = L.size();
  for (int i = 0; i < Q; i++) {
    int s = S[i];
    int e = E[i];
    for (int j = 19; j >= 0; j--) {
      if (AncL[s][j] != -1 && AncL[s][j] >= L[i]) s = AncL[s][j];
      if (AncR[e][j] != -1 && AncR[e][j] <= R[i]) e = AncR[e][j];
    }
    AddQuery(posL[s].first, posL[s].second, posR[e].first, posR[e].second);
  }

  vector<int> res(Q, 0);
  LineSweep(2 * N, res);
  for (int i = 0; i < Q; i++) res[i] = res[i] > 0;
  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51