답안 #210116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210116 2020-03-16T15:02:26 Z waynetuinfor Cats or Dogs (JOI18_catdog) C++17
0 / 100
1801 ms 524288 KB
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#include "catdog.h"

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;

void initialize(int n, std::vector<int> a, std::vector<int> b) {
  assert(n <= 15);
  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.resize(n);
  ksz.resize(n);
  to.resize(n, -1);
  fa.resize(n, -1);
  fr.resize(n, -1);
  dep.resize(n);
  tree.resize(n);

  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]);
    }
  }
}

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 cat(int v) {
  v--;
  std::vector<std::vector<int>> hist;
  for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
    hist.push_back(GetValue(w));
  }
  tree[fr[v]].Modify(dep[v] - dep[fr[v]], {0, kInf});
  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++;
    // std::cerr << "v = " << v << " fa = " << fa[v] << " upd-aux = " << aux[0]
    // << ", " << aux[1] << std::endl;
    UpdateAux(fa[v], aux);
    v = fr[fa[v]];
  }
  // for (int i = 0; i < g.size(); ++i) {
  //   auto gv = GetValue(i);
  //   std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
  //   std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
  //   auto aux = GetAux(i);
  //   std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
  //   std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
  // }
  // std::cerr << std::endl;
  auto res = GetValue(0);
  return std::min(res[0], res[1]);
}

int dog(int v) {
  v--;
  std::vector<std::vector<int>> hist;
  for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
    hist.push_back(GetValue(w));
  }
  tree[fr[v]].Modify(dep[v] - dep[fr[v]], {kInf, 0});
  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]];
  }
  // for (int i = 0; i < g.size(); ++i) {
  //   auto gv = GetValue(i);
  //   std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
  //   std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
  //   auto aux = GetAux(i);
  //   std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
  //   std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
  // }
  // std::cerr << std::endl;
  auto res = GetValue(0);
  return std::min(res[0], res[1]);
}

int neighbor(int v) {
  v--;
  std::vector<std::vector<int>> hist;
  for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
    hist.push_back(GetValue(w));
  }
  tree[fr[v]].Modify(dep[v] - dep[fr[v]], {0, 0});
  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++;
    // std::cerr << "v = " << v << " fa = " << fa[v] << " upd-aux = " << aux[0]
    // << ", " << aux[1] << std::endl;
    UpdateAux(fa[v], aux);
    v = fr[fa[v]];
  }
  // for (int i = 0; i < g.size(); ++i) {
  //   auto gv = GetValue(i);
  //   std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
  //   std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
  //   auto aux = GetAux(i);
  //   std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
  //   std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
  // }
  // std::cerr << std::endl;
  auto res = GetValue(0);
  return std::min(res[0], res[1]);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Runtime error 1801 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Runtime error 1801 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Runtime error 1801 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -