Submission #676037

#	Time	Username	Problem	Language	Result	Execution time	Memory
676037		Hegdahl	Werewolf (IOI18_werewolf)	C++17	100 / 100	981 ms	163412 KiB

werewolf

#include "werewolf.h"

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

template <class F>
struct yc {
  F f_;
  yc(F &&f) : f_(std::forward<F>(f)) {}

  decltype(auto) operator()(auto &&...args) {
    return f_(std::ref(*this), std::forward<decltype(args)>(args)...);
  }
};

struct krusk {
  vector<array<int, 18>> u;
  vector<int> l, r, lo, hi;
  vector<int> order, where;
  vector<int> lm, rm;

  krusk(int n, const vector<array<int, 2>> &e)
      : u(2 * n - 1),
        l(n - 1, -1),
        r(n - 1, -1),
        lo(2 * n - 1),
        hi(2 * n - 1),
        where(2 * n - 1, -1),
        lm(2 * n - 1, (int)1e9),
        rm(2 * n - 1, -(int)1e9) {
    vector<int> boss(n, -1), root(n);
    iota(root.begin(), root.end(), 0);
    iota(lo.begin(), lo.begin() + n, 0);
    iota(hi.begin(), hi.begin() + n, 0);
    int nxt = n;

    auto find = yc([&](auto find, int i) -> int {
      if (boss[i] < 0) return i;
      return boss[i] = find(boss[i]);
    });

    auto unite = [&](int i, int j) {
      i = find(i), j = find(j);
      if (i == j) return false;
      if (boss[i] > boss[j]) swap(i, j);
      boss[i] += boss[j];
      boss[j] = i;

      l[nxt - n] = root[i];
      r[nxt - n] = root[j];
      lo[nxt] = min(lo[root[i]], lo[root[j]]);
      hi[nxt] = max(hi[root[i]], hi[root[j]]);

      root[i] = nxt;
      root[j] = -1;

      ++nxt;
      return true;
    };

    for (auto [i, j] : e) unite(i, j);

    assert(nxt == 2 * n - 1);
    order.reserve(2 * n - 1);

    auto dfs = yc([&](auto dfs, int i, int p) -> void {
      u[i][0] = p;
      for (int lvl = 0; lvl + 1 < u[i].size(); ++lvl)
        u[i][lvl + 1] = u[u[i][lvl]][lvl];

      if (i >= n && l[i - n] >= 0) dfs(l[i - n], i);
      where[i] = (int)order.size();
      order.push_back(i);
      lm[i] = min(lm[i], where[i]);
      rm[i] = max(rm[i], where[i]);
      if (i >= n && r[i - n] >= 0) dfs(r[i - n], i);

      lm[p] = min(lm[p], lm[i]);
      rm[p] = max(rm[p], rm[i]);
    });

    dfs(nxt - 1, nxt - 1);
  }

  array<int, 2> qry(int i, int mn, int mx) {
    assert(mn <= lo[i] && hi[i] <= mx);

    for (int lvl = (int)u[i].size() - 1; lvl >= 0; --lvl) {
      int j = u[i][lvl];
      if (mn <= lo[j] && hi[j] <= mx) i = j;
    }

    return {lm[i], rm[i]};
  }
};

vector<int> check_validity(int n, vector<int> ei, vector<int> ej,
                           vector<int> starts, vector<int> targets,
                           vector<int> los, vector<int> his) {
  int m = (int)ei.size();
  assert((int)ej.size() == m);
  vector<array<int, 2>> e(m);
  for (int mm = 0; mm < m; ++mm) {
    auto &[i, j] = e[mm];
    i = ei[mm];
    j = ej[mm];
  }

  sort(e.begin(), e.end(), [&](auto e0, auto e1) {
    auto [i0, j0] = e0;
    auto [i1, j1] = e1;
    return max(i0, j0) < max(i1, j1);
  });

  auto lo_tree = krusk(n, e);

  sort(e.begin(), e.end(), [&](auto e0, auto e1) {
    auto [i0, j0] = e0;
    auto [i1, j1] = e1;
    return min(i0, j0) > min(i1, j1);
  });

  auto hi_tree = krusk(n, e);

  int q = (int)starts.size();
  assert(q == (int)targets.size());
  assert(q == (int)los.size());
  assert(q == (int)his.size());
  vector<int> ans(q);

  int offset = 1;
  while (offset < 2 * n - 1) offset *= 2;

  vector<basic_string<int>> st(2 * offset);

  for (int i = 0; i < n; ++i)
    st[offset + hi_tree.where[i]].push_back(lo_tree.where[i]);
  for (int I = offset - 1; I; --I)
    std::merge(st[2 * I].begin(), st[2 * I].end(), st[2 * I + 1].begin(),
               st[2 * I + 1].end(), back_inserter(st[I]));
  
  auto check = [&](const auto &v, int lo, int hi) {
    auto it0 = lower_bound(v.begin(), v.end(), lo);
    auto it1 = upper_bound(v.begin(), v.end(), hi);
    return it0 != it1;
  };

  auto qry = [&](int i, int j, int x, int y) {
    i += offset - 1;
    j += offset + 1;
    while (i + 1 < j) {
      if (i % 2 == 0 && check(st[i + 1], x, y)) return true;
      if (j % 2 == 1 && check(st[j - 1], x, y)) return true;
      i >>= 1, j >>= 1;
    }
    return false;
  };
  
  for (int qq = 0; qq < q; ++qq) {
    int s = starts[qq];
    int t = targets[qq];
    int lo = los[qq];
    int hi = his[qq];

    auto [sl, sr] = hi_tree.qry(s, lo, n - 1);
    auto [tl, tr] = lo_tree.qry(t, 0, hi);

    ans[qq] = qry(sl, sr, tl, tr);
  }

  return ans;
}

Compilation message (stderr)

werewolf.cpp:11:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   11 |   decltype(auto) operator()(auto &&...args) {
      |                             ^~~~
werewolf.cpp: In instantiation of 'krusk::krusk(int, const std::vector<std::array<int, 2> >&)::<lambda(auto:25, int, int)> [with auto:25 = std::reference_wrapper<yc<krusk::krusk(int, const std::vector<std::array<int, 2> >&)::<lambda(auto:25, int, int)> > >]':
werewolf.cpp:12:14:   required from 'decltype(auto) yc<F>::operator()(auto:23&& ...) [with auto:23 = {int, int}; F = krusk::krusk(int, const std::vector<std::array<int, 2> >&)::<lambda(auto:25, int, int)>]'
werewolf.cpp:82:25:   required from here
werewolf.cpp:68:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 18>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |       for (int lvl = 0; lvl + 1 < u[i].size(); ++lvl)
      |                         ~~~~~~~~^~~~~~~~~~~~~

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