Submission #990330

#	Time	Username	Problem	Language	Result	Execution time	Memory
990330		four_specks	Werewolf (IOI18_werewolf)	C++17	100 / 100	400 ms	69992 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

namespace {

template <typename Fun>
struct YCombinator {
  template <typename T>
  YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun(ref(*this), forward<Args>(args)...);
  }

 private:
  Fun fun;
};

template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;

template <typename S, typename Op = plus<S>>
struct FenwickTree {
  explicit FenwickTree(int _n = 0, S _e = S(), Op _op = Op()) : n(_n), e(_e), op(_op), tree(n + 1, e) {}

  S query(int p) const {
    S x = e;
    for (; p; p -= p & -p) {
      x = op(tree[p], x);
    }
    return x;
  }

  S query() const {
    return query(n);
  }

  void modify(int p, S x) {
    for (p++; p <= n; p += p & -p) {
      tree[p] = op(tree[p], x);
    }
  }

  int size() const {
    return n;
  }

 private:
  int n;
  S e;
  Op op;
  vector<S> tree;
};

}  // namespace

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 n = N;
  int m = (int)X.size();
  int q = (int)S.size();
  vector<int> a, b;
  vector<array<int, 2>> sub_a(q), sub_b(q);
  vector<vector<int>> qrys_l(n), qrys_r(n);
  for (int i = 0; i < q; i++) {
    qrys_l[L[i]].push_back(i);
    qrys_r[R[i]].push_back(i);
  }
  {
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
      int u = X[i];
      int v = Y[i];
      if (u > v) {
        swap(u, v);
      }
      adj[u].push_back(v);
    }
    vector<vector<int>> krt(2 * n);
    vector<int> node(q);
    vector<int> root(2 * n);
    iota(root.begin(), root.end(), 0);
    YCombinator get_root = [&](auto self, int u) -> int {
      return root[u] == u ? u : root[u] = self(root[u]);
    };
    for (int u = n - 1; u >= 0; u--) {
      int x = 2 * n - (u + 1);
      krt[x].push_back(u);
      root[u] = x;
      vector<int> ch;
      for (int v : adj[u]) {
        ch.push_back(get_root(v));
      }
      sort(ch.begin(), ch.end());
      ch.erase(unique(ch.begin(), ch.end()), ch.end());
      for (int y : ch) {
        krt[x].push_back(y);
        root[y] = x;
      }
      for (int i : qrys_l[u]) {
        node[i] = get_root(S[i]);
      }
    }
    vector<int> tin(2 * n), tout(2 * n);
    {
      int timer = 0;
      YCombinator([&](auto self, int x) -> void {
        tin[x] = timer;
        if (x < n) {
          a.push_back(x);
          timer++;
        }
        for (int y : krt[x]) {
          self(y);
        }
        tout[x] = timer;
      })(2 * n - 1);
    }
    for (int i = 0; i < q; i++) {
      sub_a[i] = {tin[node[i]], tout[node[i]]};
    }
  }
  {
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
      int u = X[i];
      int v = Y[i];
      if (u < v) {
        swap(u, v);
      }
      adj[u].push_back(v);
    }
    vector<vector<int>> krt(2 * n);
    vector<int> node(q);
    vector<int> root(2 * n);
    iota(root.begin(), root.end(), 0);
    YCombinator get_root = [&](auto self, int u) -> int {
      return root[u] == u ? u : root[u] = self(root[u]);
    };
    for (int u = 0; u < N; u++) {
      int x = n + u;
      krt[x].push_back(u);
      root[u] = x;
      vector<int> ch;
      for (int v : adj[u]) {
        ch.push_back(get_root(v));
      }
      sort(ch.begin(), ch.end());
      ch.erase(unique(ch.begin(), ch.end()), ch.end());
      for (int y : ch) {
        krt[x].push_back(y);
        root[y] = x;
      }
      for (int i : qrys_r[u]) {
        node[i] = get_root(E[i]);
      }
    }
    vector<int> tin(2 * n), tout(2 * n);
    {
      int timer = 0;
      YCombinator([&](auto self, int x) -> void {
        tin[x] = timer;
        if (x < n) {
          b.push_back(x);
          timer++;
        }
        for (int y : krt[x]) {
          self(y);
        }
        tout[x] = timer;
      })(2 * n - 1);
    }
    for (int i = 0; i < q; i++) {
      sub_b[i] = {tin[node[i]], tout[node[i]]};
    }
  }
  vector<int> ans(q);
  {
    vector<int> idx(n);
    for (int i = 0; i < n; i++) {
      idx[a[i]] = i;
    }
    vector<array<vector<int>, 2>> todo(n);
    for (int i = 0; i < q; i++) {
      todo[sub_b[i][0]][0].push_back(i);
      todo[sub_b[i][1] - 1][1].push_back(i);
    }
    FenwickTree<int> fenw(n);
    for (int i = 0; i < n; i++) {
      for (int j : todo[i][0]) {
        ans[j] -= fenw.query(sub_a[j][1]) - fenw.query(sub_a[j][0]);
      }
      fenw.modify(idx[b[i]], 1);
      for (int j : todo[i][1]) {
        ans[j] += fenw.query(sub_a[j][1]) - fenw.query(sub_a[j][0]);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (ans[i] > 0) {
      ans[i] = 1;
    }
  }
  return ans;
}

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