oj.uz

Submission #352309

# Submission time Handle Problem Language Result Execution time Memory
352309 2021-01-20T14:58:28 Z KoD Cats or Dogs (JOI18_catdog) C++17
0 / 100
 4 ms 5868 KB 
#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;
  constexpr long long INF = 1000000000000000;

  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{ { INF, INF, INF, INF }};
      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) {
      for (int i = 0; i < size; ++i) {
        data[i + size] = Monoid::ID();
      }
      for (int i = size - 1; i > 0; --i) {
        fix(i);
      }
    }

    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{ INF, INF };
      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 != p) {
        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(label[u] + 1);
      trees[v].set(label[u], arr);
      const auto next = trees[v].get(label[u] + 1);
      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) {
  return Solver::set(v, std::array<long long, 2>{ Solver::vals[v][0], Solver::MAX });
}

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

int neighbor(int v) {
  return Solver::set(v, Solver::vals[v]);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Incorrect 4 ms 5868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Incorrect 4 ms 5868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Incorrect 4 ms 5868 KB Output isn't correct
3 Halted 0 ms 0 KB -