Submission #907587

#	Time	Username	Problem	Language	Result	Execution time	Memory
907587		evenvalue	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	1 ms	348 KiB

catdog

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

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

template<class node, class F = std::function<node(const node &, const node &)>>
class SegTree {
  int n = 0;
  std::vector<node> t;
  F unite;

  void build(const int x, const int l, const int r, const std::vector<node> &a) {
    if (l == r) {
      t[x] = a[l];
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    build(x + 1, l, mid, a);
    build(y, mid + 1, r, a);
    t[x] = unite(t[x + 1], t[y]);
  }

  void update(const int x, const int l, const int r, const int p, const node &v) {
    if (l == p and p == r) {
      t[x] = v;
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (p <= mid) {
      update(x + 1, l, mid, p, v);
    } else {
      update(y, mid + 1, r, p, v);
    }
    t[x] = unite(t[x + 1], t[y]);
  }

  node query(const int x, const int l, const int r, const int ql, const int qr) const {
    if (ql <= l and r <= qr) {
      return t[x];
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (qr <= mid) {
      return query(x + 1, l, mid, ql, qr);
    } else if (mid < ql) {
      return query(y, mid + 1, r, ql, qr);
    } else {
      return unite(query(x + 1, l, mid, ql, qr), query(y, mid + 1, r, ql, qr));
    }
  }

public:
  SegTree() = default;
  explicit SegTree(const int n, const node e, F f) : n(n), t(2 * n - 1, e), unite(std::move(f)) {}
  explicit SegTree(const std::vector<node> &a, F f) : n(a.size()), t(2 * (a.size()) - 1), unite(std::move(f)) {
    build(0, 0, n - 1, a);
  }

  void update(const int p, const node &v) {
    assert(0 <= p and p < n);
    update(0, 0, n - 1, p, v);
  }

  [[nodiscard]] node query(const int l, const int r) const {
    assert(0 <= l and l <= r and r < n);
    return query(0, 0, n - 1, l, r);
  }
};

class HeavyLight {
  int n;
  vector<vector<int>> g;

public:
  vector<int> parent;
  vector<int> heavy;
  vector<int> depth;
  vector<int> in;
  vector<int> out;
  vector<int> head;
  vector<int> size;

private:
  void dfs(const int x) {
    size[x] = 1;
    int max_size = 0;
    for (const int y : g[x]) {
      if (y == parent[x]) continue;
      depth[y] = depth[x] + 1;
      parent[y] = x;
      dfs(y);
      if (size[y] > max_size) {
        heavy[x] = y;
        max_size = size[y];
      }
      size[x] += size[y];
    }
  }

  int timer = 0;
  void dfs2(const int x) {
    head[x] = (parent[x] == -1 or heavy[parent[x]] != x ? x : head[parent[x]]);
    in[x] = timer++;
    if (heavy[x] != -1) {
      dfs2(heavy[x]);
    }
    for (const int y : g[x]) {
      if (y == parent[x] or y == heavy[x]) continue;
      dfs2(y);
    }
    out[x] = timer - 1;
  }

public:
  HeavyLight() = default;
  explicit HeavyLight(const vector<vector<int>> &t)
      : n(t.size()), g(t),
        parent(n, -1), heavy(n, -1), depth(n),
        in(n), out(n), head(n), size(n) {
    dfs(0);
    dfs2(0);
  }

  template<class Op = function<void(int, int)>>
  void operate(int x, int y, const Op &op, const bool ignore_lca = false) {
    while (head[x] != head[y]) {
      if (depth[head[x]] > depth[head[y]]) swap(x, y);
      op(in[head[y]], in[y]);
      y = parent[head[y]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    if (in[x] + ignore_lca <= in[y]) op(in[x] + ignore_lca, in[y]);
  }
};

class node {
  array<array<int, 2>, 2> a;

public:
  node(const int x = 0) {
    for (const int i : {0, 1}) {
      for (const int j : {0, 1}) {
        a[i][j] = x;
      }
    }
  }

  array<int, 2> &operator[](const int i) {
    return a[i];
  }
};

int n = -1;
SegTree<node> st;
HeavyLight hld;

void initialize(const int N, vector<int> A, vector<int> B) {
  n = N;

  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    A[i]--, B[i]--;
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }

  auto unite = [](node l, node r) {
    node ans(kInf);
    for (const int s1 : {0, 1}) {
      for (const int s2 : {0, 1}) {
        for (const int e1 : {0, 1}) {
          for (const int e2 : {0, 1}) {
            ans[s1][e2] = min(ans[s1][e2], l[s1][e1] + (e1 != s2) + r[s2][e2]);
          }
        }
      }
    }
    return ans;
  };

  st = SegTree<node>(n, node(), unite);
  hld = HeavyLight(g);
}

int cat(const int x) {
  node cur(kInf);
  cur[0][0] = 0;

  hld.operate(x - 1, x - 1, [&](const int l, const int r) {
    st.update(l, cur);
  });

  node ans = st.query(0, n - 1);
  return min({
      ans[0][0], ans[0][1],
      ans[1][0], ans[1][1]
  });
}

int dog(const int x) {
  node cur(kInf);
  cur[1][1] = 0;

  hld.operate(x - 1, x - 1, [&](const int l, const int r) {
    st.update(l, cur);
  });

  node ans = st.query(0, n - 1);
  return min({
      ans[0][0], ans[0][1],
      ans[1][0], ans[1][1]
  });
}

int neighbor(const int x) {
  node cur(0);

  hld.operate(x - 1, x - 1, [&](const int l, const int r) {
    st.update(l, cur);
  });

  node ans = st.query(0, n - 1);
  return min({
      ans[0][0], ans[0][1],
      ans[1][0], ans[1][1]
  });
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62