Submission #210124

#	Time	Username	Problem	Language	Result	Execution time	Memory
210124		waynetuinfor	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1040 ms	51064 KiB

catdog

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#include "catdog.h"

namespace {

constexpr int kInf = 1'000'000;

std::vector<std::vector<int>> g, nd;
std::vector<int> sz, to, fa, fr, dep, ksz;

void Dfs(int x, int p) {
  sz[x] = 1;
  fa[x] = p;
  for (int u : g[x]) {
    if (u == p) continue;
    dep[u] = dep[x] + 1;
    Dfs(u, x);
    sz[x] += sz[u];
    if (to[x] == -1 || sz[u] > sz[to[x]]) to[x] = u;
  }
}

void Link(int x, int f) {
  fr[x] = f;
  if (to[x] != -1) Link(to[x], f);
  for (int u : g[x]) {
    if (u == fa[x] || u == to[x]) continue;
    Link(u, u);
  }
}

struct IntervalTree {
  int n;
  std::vector<std::vector<int>> tree;
  std::vector<std::vector<int>> aux;

  IntervalTree() = default;
  IntervalTree(int n)
      : n(n), tree(n * 4, std::vector<int>(4)), aux(n, std::vector<int>(2)) {
    for (auto &v : tree) {
      v[1] = kInf;
      v[2] = kInf;
    }
  }

  std::vector<int> Merge(const std::vector<int> &a, const std::vector<int> &b,
                         int p) {
    std::vector<int> res(4, kInf);
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        res[(i & 2) | (j & 1)] = std::min(
            res[(i & 2) | (j & 1)],
            a[i] + b[j] + ((i & 1) != (j >> 1 & 1)) + aux[p][j >> 1 & 1]);
      }
    }
    return res;
  }

  void UpdateAux(int p, const std::vector<int> &v) {
    auto Impl = [&](auto self, int l, int r, int o = 0) {
      if (r - l == 1) {
        aux[l] = v;
        return;
      }
      int m = (l + r) >> 1;
      if (p < m) {
        self(self, l, m, o * 2 + 1);
      } else {
        self(self, m, r, o * 2 + 2);
      }
      tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2], m);
    };
    Impl(Impl, 0, n);
  }

  void Modify(int p, const std::vector<int> &v) {
    auto Impl = [&](auto self, int l, int r, int o = 0) {
      if (r - l == 1) {
        std::fill(tree[o].begin(), tree[o].end(), kInf);
        for (int i = 0; i < 2; ++i) tree[o][i << 1 | i] = v[i];
        return;
      }
      int m = (l + r) >> 1;
      if (p < m) {
        self(self, l, m, o * 2 + 1);
      } else {
        self(self, m, r, o * 2 + 2);
      }
      tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2], m);
    };
    Impl(Impl, 0, n);
  }

  std::vector<int> Query(int ql, int qr) {
    auto Impl = [&](auto self, int l, int r, int o = 0) {
      if (l >= ql && r <= qr) return tree[o];
      int m = (l + r) >> 1;
      if (qr <= m) return self(self, l, m, o * 2 + 1);
      if (ql >= m) return self(self, m, r, o * 2 + 2);
      return Merge(self(self, l, m, o * 2 + 1), self(self, m, r, o * 2 + 2), m);
    };
    return Impl(Impl, 0, n);
  }
};

std::vector<IntervalTree> tree;

}  // namespace

void initialize(int n, std::vector<int> a, std::vector<int> b) {
  g.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    int u = a[i], v = b[i];
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  sz.assign(n, 0);
  ksz.assign(n, 0);
  to.assign(n, -1);
  fa.assign(n, -1);
  fr.assign(n, -1);
  dep.assign(n, 0);
  tree.assign(n, IntervalTree());

  Dfs(0, -1);
  Link(0, 0);

  for (int i = 0; i < n; ++i) ksz[fr[i]]++;
  for (int i = 0; i < n; ++i) {
    if (fr[i] == i) {
      tree[i] = IntervalTree(ksz[i]);
    }
  }
}

namespace {

std::vector<int> GetAux(int v) {
  int p = dep[v] - dep[fr[v]];
  return tree[fr[v]].aux[p];
}

std::vector<int> GetValue(int v) {
  int p = dep[v] - dep[fr[v]];
  auto val = tree[fr[v]].Query(p, ksz[fr[v]]);
  std::vector<int> res(2, kInf);
  for (int i = 0; i < 4; ++i) {
    res[i >> 1 & 1] = std::min(res[i >> 1 & 1], val[i]);
  }
  for (int i = 0; i < 2; ++i) res[i] += GetAux(v)[i];
  return res;
}

void UpdateAux(int v, const std::vector<int> &aux) {
  int p = dep[v] - dep[fr[v]];
  tree[fr[v]].UpdateAux(p, aux);
}

int Exec(int v, std::vector<int> upd) {
  std::vector<std::vector<int>> hist;
  for (int w = fr[v]; fa[w] != -1; w = fr[fa[w]]) {
    hist.push_back(GetValue(w));
  }
  tree[fr[v]].Modify(dep[v] - dep[fr[v]], upd);
  v = fr[v];
  int ptr = 0;
  while (fa[v] >= 0) {
    auto aux = GetAux(fa[v]);
    auto old = hist[ptr];
    aux[0] -= std::min(old[0], old[1] + 1);
    aux[1] -= std::min(old[1], old[0] + 1);
    auto upd = GetValue(v);
    aux[0] += std::min(upd[0], upd[1] + 1);
    aux[1] += std::min(upd[1], upd[0] + 1);
    ptr++;
    UpdateAux(fa[v], aux);
    v = fr[fa[v]];
  }
  auto res = GetValue(0);
  return std::min(res[0], res[1]);
}

}  // namespace

int cat(int v) { return Exec(v - 1, {0, kInf}); }

int dog(int v) { return Exec(v - 1, {kInf, 0}); }

int neighbor(int v) { return Exec(v - 1, {0, 0}); }

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