제출 #357732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
357732		KoD	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	627 ms	27392 KiB

catdog

#include "catdog.h"

#include <vector>
#include <algorithm>
#include <utility>
#include <array>

namespace Solver {
  template <class T>
  using Vec = std::vector<T>;

  constexpr int MAX = 100000;

  struct Monoid {
    static constexpr Monoid ID() { return Monoid { { 0, MAX, MAX, 0 } }; }
    std::array<std::array<long long, 2>, 2> value;

    Monoid operator + (const Monoid &other) const {
      Monoid ret{ { MAX, MAX, MAX, MAX }};
      for (int i: { 0, 1 }) {
        for (int j: { 0, 1 }) {
          for (int k: { 0, 1 }) {
            for (int l: { 0, 1 }) {
              ret.value[i][l] = std::min(ret.value[i][l], value[i][j] + other.value[k][l] + (j ^ k));
            }
          }
        }
      }
      return ret;
    }
  };

  struct Segtree {
    int size;
    Vec<Monoid> data;

    void fix(const int k) {
      data[k] = data[k << 1 | 0] + data[k << 1 | 1];
    }

    Segtree(const int n = 0): size(n), data(2 * n, Monoid::ID()) { }

    void set(int k, const std::array<long long, 2> &arr) {
      k += size;
      data[k].value[0][0] = arr[0];
      data[k].value[1][1] = arr[1];
      while (k > 1) {
        k >>= 1;
        fix(k);
      }
    }

    std::array<long long, 2> get(int r) const {
      int l = size;
      r += size;
      Monoid ml = Monoid::ID();
      Monoid mr = Monoid::ID();
      while (l < r) {
        if (l & 1) {
          ml = ml + data[l];
          l += 1;
        }
        if (r & 1) {
          r -= 1;
          mr = data[r] + mr;
        }
        l >>= 1;
        r >>= 1;
      }
      Monoid tmp = ml + mr;
      std::array<long long, 2> ret{ MAX, MAX };
      for (int i: { 0, 1 }) {
        for (int j: { 0, 1 }) {
          ret[i] = std::min(ret[i], tmp.value[i][j]);
        }
      }
      return ret;
    }
  };

  std::array<Vec<int>, MAX> graph;
  std::array<int, MAX> parent, size, head, label, state;
  std::array<Segtree, MAX> trees;
  std::array<std::array<long long, 2>, MAX> vals;

  void precalc(const int u, const int p) {
    parent[u] = p;
    size[u] = 1;
    for (const auto v: graph[u]) {
      if (v != parent[u]) {
        precalc(v, u);
        size[u] += size[v];
      }
    }
  }

  void decomp(const int u, const int h, const int l) {
    head[u] = h;
    label[u] = l;
    int c = -1;
    for (const auto v: graph[u]) {
      if (v != parent[u]) {
        if (c == -1 || size[c] < size[v]) {
          c = v;
        }
      }
    }
    if (c == -1) {
      trees[h] = Segtree(l + 1);
    }
    else {
      decomp(c, h, l + 1);
      for (const auto v: graph[u]) {
        if (v != parent[u] && v != c) {
          decomp(v, v, 0);
        }
      }
    }
  }

  long long set(int u, std::array<long long, 2> arr) {
    while (true) {
      const auto v = head[u];
      const auto cur = trees[v].get(trees[v].size);
      trees[v].set(label[u], arr);
      const auto next = trees[v].get(trees[v].size);
      if (v == 0) {
        break;
      }
      u = parent[v];
      for (int i: { 0, 1 }) {
        vals[u][i] -= std::min(cur[i], cur[i ^ 1] + 1);
        vals[u][i] += std::min(next[i], next[i ^ 1] + 1);
        arr[i] = (state[u] == 2 - i ? (long long) MAX : vals[u][i]);
      }
    }
    const auto tmp = trees[0].get(trees[0].size);
    return std::min(tmp[0], tmp[1]);
  }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
  for (int i = 0; i < N - 1; ++i) {
    A[i] -= 1;
    B[i] -= 1;
    Solver::graph[A[i]].push_back(B[i]);
    Solver::graph[B[i]].push_back(A[i]);
  }
  Solver::precalc(0, -1);
  Solver::decomp(0, 0, 0);
}

int cat(int v) {
  using namespace Solver;
  v -= 1;
  state[v] = 1;
  return set(v, std::array<long long, 2>{ vals[v][0], MAX });
}

int dog(int v) {
  using namespace Solver;
  v -= 1;
  state[v] = 2;
  return set(v, std::array<long long, 2>{ MAX, vals[v][1] });
}

int neighbor(int v) {
  using namespace Solver;
  v -= 1;
  state[v] = 0;
  return set(v, vals[v]);
}

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