Submission #102848

#	Time	Username	Problem	Language	Result	Execution time	Memory
102848		wxh010910	Werewolf (IOI18_werewolf)	C++17	100 / 100	1883 ms	126920 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

template<typename T> class fenwick_t {
 public:
  vector<T> fenw;
  int n;

  fenwick_t(int n):n(n) {
    fenw.resize(n);
  }

  void modify(int x, T value) {
    while (x < n) {
      fenw[x] += value;
      x |= x + 1;
    }
  }

  T query(int x) {
    T result{};
    while (x >= 0) {
      result += fenw[x];
      x = (x & x + 1) - 1;
    }
    return result;
  }
};

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();

  struct tree_t {
    struct edge_t {
      int u, v, w;

      edge_t(int u = 0, int v = 0, int w = 0):u(u), v(v), w(w) {
      }

      bool operator < (const edge_t &b) const {
        return w < b.w;
      }
    };

    vector<int> l, r, left, right, value;
    vector<vector<int>> ancestor;
    int n, log_n, total, counter;
    vector<edge_t> edge;
    
    tree_t(int n):n(n) {
      l = r = left = right = value = vector<int> ((n << 1) - 1, -1);
      total = n;
      log_n = counter = 0;
      while (1 << log_n <= n) {
        ++log_n;
      }
      ancestor = vector<vector<int>> (log_n, vector<int> ((n << 1) - 1, -1));
    }

    void dfs(int x) {
      left[x] = counter++;
      if (x >= n) {
        dfs(l[x]);
        dfs(r[x]);
      }
      right[x] = counter;
    }

    void init() {
      sort(edge.begin(), edge.end());
      vector<int> p((n << 1) - 1);
      for (int i = 0; i < (n << 1) - 1; ++i) {
        p[i] = i;
      }
      function<int(int)> find = [&](int x) {
        while (x != p[x]) {
          x = p[x] = p[p[x]];
        }
        return x;
      };
      
      total = n;
      for (auto e : edge) {
        if (find(e.u) != find(e.v)) {
          l[total] = find(e.u);
          r[total] = find(e.v);
          ancestor[0][find(e.u)] = ancestor[0][find(e.v)] = total;
          value[total] = e.w;
          p[find(e.u)] = p[find(e.v)] = total;
          total++;
        }
      }
      for (int i = 1; i < log_n; ++i) {
        for (int j = 0; j < (n << 1) - 1; ++j) {
          if (~ancestor[i - 1][j]) {
            ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
          }
        }
      }
      dfs(n - 1 << 1);
    }

    int go(int x, int limit) {
      for (int i = log_n - 1; ~i; --i) {
        if (~ancestor[i][x] && value[ancestor[i][x]] <= limit) {
          x = ancestor[i][x];
        }
      }
      return x;
    }
  };

  tree_t prefix(n), suffix(n);
  for (int i = 0; i < m; ++i) {
    prefix.edge.emplace_back(x[i], y[i], max(x[i], y[i]));
    suffix.edge.emplace_back(x[i], y[i], -min(x[i], y[i]));
  }
  prefix.init();
  suffix.init();

  vector<pair<int, int>> points;
  fenwick_t<int> fenwick((n << 1) - 1);
  for (int i = 0; i < n; ++i) {
    points.emplace_back(prefix.left[i], suffix.left[i]);
  }
  sort(points.begin(), points.end());

  struct event_t {
    int x, l, r, id, sign;

    event_t(int x = 0, int l = 0, int r = 0, int id = 0, int sign = 0):x(x), l(l), r(r), id(id), sign(sign) {
    }

    bool operator < (const event_t &b) const {
      return x < b.x;
    }
  };

  vector<event_t> events;
  vector<int> answer(q);

  for (int i = 0; i < q; ++i) {
    int x = prefix.go(e[i], r[i]), y = suffix.go(s[i], -l[i]);
    events.emplace_back(prefix.left[x], suffix.left[y], suffix.right[y], i, -1);
    events.emplace_back(prefix.right[x], suffix.left[y], suffix.right[y], i, 1);
  }
  sort(events.begin(), events.end());
  int current = 0;
  for (auto event : events) {
    while (current < n && points[current].first < event.x) {
      fenwick.modify(points[current++].second, 1);
    }
    answer[event.id] += event.sign * (fenwick.query(event.r - 1) - fenwick.query(event.l - 1));
  }
  for (int i = 0; i < q; ++i) {
    if (answer[i]) {
      answer[i] = 1;
    }
  }
  return answer;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::tree_t::init()':
werewolf.cpp:102:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
       dfs(n - 1 << 1);
           ~~^~~
werewolf.cpp: In instantiation of 'T fenwick_t<T>::query(int) [with T = int]':
werewolf.cpp:155:64:   required from here
werewolf.cpp:26:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
       x = (x & x + 1) - 1;
                ~~^~~

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