結果

問題 No.1215 都市消滅ビーム
ユーザー noshi91noshi91
提出日時 2020-08-30 16:32:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,178 ms / 6,000 ms
コード長 9,432 bytes
コンパイル時間 1,573 ms
コンパイル使用メモリ 103,508 KB
実行使用メモリ 27,264 KB
最終ジャッジ日時 2024-11-17 10:02:56
合計ジャッジ時間 36,975 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 501 ms
10,136 KB
testcase_14 AC 714 ms
10,004 KB
testcase_15 AC 1,845 ms
19,864 KB
testcase_16 AC 445 ms
8,336 KB
testcase_17 AC 738 ms
16,976 KB
testcase_18 AC 785 ms
13,408 KB
testcase_19 AC 73 ms
5,248 KB
testcase_20 AC 1,452 ms
16,184 KB
testcase_21 AC 24 ms
5,248 KB
testcase_22 AC 1,123 ms
13,428 KB
testcase_23 AC 1,053 ms
17,048 KB
testcase_24 AC 874 ms
12,376 KB
testcase_25 AC 538 ms
11,104 KB
testcase_26 AC 1,052 ms
17,552 KB
testcase_27 AC 1,175 ms
20,388 KB
testcase_28 AC 731 ms
9,568 KB
testcase_29 AC 642 ms
9,684 KB
testcase_30 AC 367 ms
16,416 KB
testcase_31 AC 243 ms
7,784 KB
testcase_32 AC 118 ms
14,920 KB
testcase_33 AC 111 ms
13,500 KB
testcase_34 AC 3,178 ms
27,140 KB
testcase_35 AC 3,118 ms
27,264 KB
testcase_36 AC 3,079 ms
27,136 KB
testcase_37 AC 2,694 ms
27,172 KB
testcase_38 AC 2,624 ms
27,044 KB
testcase_39 AC 2,993 ms
27,176 KB
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define NDEBUG

#pragma region cp_template

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include <limits>

namespace n91 {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;
  using isize = std::ptrdiff_t;
  using usize = std::size_t;

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept : i(i) {}
      void operator++() noexcept { ++i; }
      constexpr usize operator*() const noexcept { return i; }
      constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
      : f(std::min(f, l)), l(l) {}
    constexpr auto begin() const noexcept { return f; }
    constexpr auto end() const noexcept { return l; }
  };
  struct revrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept : i(i) {}
      void operator++() noexcept { --i; }
      constexpr usize operator*() const noexcept { return i; }
      constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
    };
    const itr f, l;
    constexpr revrep(const usize f, const usize l) noexcept
      : f(l - 1), l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept { return f; }
    constexpr auto end() const noexcept { return l; }
  };
  template <class T> auto md_vec(const usize n, const T& value) {
    return std::vector<T>(n, value);
  }
  template <class... Args> auto md_vec(const usize n, Args... args) {
    return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
  }
  template <class T> constexpr T difference(const T& a, const T& b) noexcept {
    return a < b ? b - a : a - b;
  }
  template <class T> void chmin(T& a, const T& b) noexcept {
    if (b < a)
      a = b;
  }
  template <class T> void chmax(T& a, const T& b) noexcept {
    if (a < b)
      a = b;
  }
  template <class F> class rec_lambda {
    F f;

  public:
    rec_lambda(F&& f) : f(std::move(f)) {}
    template <class... Args> auto operator()(Args&&... args) const {
      return f(*this, std::forward<Args>(args)...);
    }
  };
  template <class F> auto make_rec(F&& f) { return rec_lambda<F>(std::move(f)); }
  template <class T> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
  }
  constexpr char eoln = '\n';
  template <class T> T ceildiv(const T& l, const T& r) {
    return l / r + (l % r != 0 ? 1 : 0);
  }

} // namespace n91

#pragma endregion cp_template

namespace kopricky {

  using namespace std;
  template <typename T> class segtree {
  private:
    int n, sz;
    vector<pair<T, int>> node;

  public:
    void resize(vector<T>& v) {
      sz = (int)v.size();
      n = 1;
      while (n < sz) {
        n *= 2;
      }
      node.resize(2 * n);
      for (int i = 0; i < sz; i++) {
        node[i + n] = make_pair(v[i], i);
      }
      for (int i = n - 1; i >= 1; i--) {
        node[i] = min(node[2 * i], node[2 * i + 1]);
      }
    }
    void update(int k, T a) {
      node[k += n] = make_pair(a, k);
      while (k >>= 1) {
        node[k] = min(node[2 * k], node[2 * k + 1]);
      }
    }
    pair<T, int> query(int a, int b) {
      pair<T, int> res1 = make_pair(numeric_limits<T>::max(), -1);
      pair<T, int> res2 = make_pair(numeric_limits<T>::max(), -1);
      a += n, b += n;
      while (a != b) {
        if (a % 2)
          res1 = min(res1, node[a++]);
        if (b % 2)
          res2 = min(res2, node[--b]);
        a >>= 1, b >>= 1;
      }
      return min(res1, res2);
    }
  };

  class LCA {
  private:
    int V;
    vector<vector<int>> G;
    vector<int> ord, depth, id;
    segtree<int> st;
    void dfs(int u, int p, int k) {
      id[u] = (int)ord.size();
      ord.push_back(u);
      depth[u] = k;
      for (int v : G[u]) {
        if (v != p) {
          dfs(v, u, k + 1);
          ord.push_back(u);
        }
      }
    }

  public:
    LCA(int node_size) : V(node_size), G(V), depth(V), id(V, -1) {}
    void add_edge(int from, int to) {
      G[from].push_back(to), G[to].push_back(from);
    }
    void build() {
      ord.reserve(2 * V - 2);
      for (int i = 0; i < V; i++) {
        if (id[i] < 0) {
          dfs(i, -1, 0);
        }
      }
      vector<int> stvec(2 * V - 2);
      for (int i = 0; i < 2 * V - 2; i++) {
        stvec[i] = depth[ord[i]];
      }
      st.resize(stvec);
    }
    int lca(int u, int v) {
      return ord[st.query(min(id[u], id[v]), max(id[u], id[v]) + 1).second];
    }
    int dist(int u, int v) {
      int lca_ = lca(u, v);
      return depth[u] + depth[v] - 2 * depth[lca_];
    }
  };

} // namespace kopricky

#include <numeric>

#define dump(x) std::cout << #x << " = " << x << std::endl;

template <class T> void dv(const std::vector<T>& v) {
  for (const auto& e : v) {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

namespace n91 {

  struct segtree {
    std::vector<i64> val;
    usize n;
    std::vector<usize> c;
    segtree(std::vector<i64> v) : val(std::move(v)), n(val.size()), c(n * 2) {
      std::sort(val.begin(), val.end());
    }
    void add(i64 i_, usize x) {
      usize i = std::lower_bound(val.begin(), val.end(), i_) - val.begin();
      i += n;
      while (i != 0) {
        c[i] += x;
        i /= 2;
      }
    }
    usize sum(i64 r_) {
      usize l = 0;
      usize r = std::lower_bound(val.begin(), val.end(), r_) - val.begin();
      l += n;
      r += n;
      usize ret = 0;
      while (l != r) {
        if (l % 2 != 0) {
          ret += c[l];
          ++l;
        }
        l /= 2;
        if (r % 2 != 0) {
          --r;
          ret += c[r];
        }
        r /= 2;
      }
      return ret;
    }
    void clear() { std::fill(c.begin(), c.end(), 0); }
  };

  void main_() {
    /*
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //*/
    const usize n = scan<usize>();
    const usize k = scan<usize>();
    std::vector<usize> c(k);
    for (auto& e : c) {
      std::cin >> e;
      --e;
    }
    std::vector<i64> d(k);
    for (auto& e : d) {
      std::cin >> e;
    }
    kopricky::LCA lca(n);
    for (const usize i : rep(0, n - 1)) {
      const usize a = scan<usize>() - 1;
      const usize b = scan<usize>() - 1;
      lca.add_edge(a, b);
    }
    lca.build();
    std::vector<i64> depth(n);
    for (const usize i : rep(0, n)) {
      depth[i] = lca.dist(0, i);
    }

    const i64 dsum = std::accumulate(d.begin(), d.end(), i64(0));
    usize all_lca = c[0];
    for (auto e : c) {
      all_lca = lca.lca(all_lca, e);
    }

    std::vector<i64> score_base;
    std::vector<i64> depth_left(k);
    std::vector<i64> sum_left(k);
    std::vector<i64> depth_right(k);
    std::vector<i64> sum_right(k);
    const usize bot = lca.lca(c[0], c[k - 1]);
    {
      // left
      depth_left[0] = depth[bot];
      sum_left[0] = d[0];
      usize lc = c[0];
      i64 sum = d[0];
      for (const usize i : rep(1, k)) {
        score_base.push_back(sum + depth[lc]);
        lc = lca.lca(lc, c[i]);
        sum += d[i];
        depth_left[i] = depth[lca.lca(lc, bot)];
        sum_left[i] = sum;
      }
    }
    {
      // right
      depth_right[k - 1] = depth[bot];
      sum_right[k - 1] = d[k - 1];
      usize lc = c[k - 1];
      i64 sum = d[k - 1];
      for (const usize i : revrep(0, k - 1)) {
        score_base.push_back(sum + depth[lc]);
        lc = lca.lca(lc, c[i]);
        sum += d[i];
        depth_right[i] = depth[lca.lca(lc, bot)];
        sum_right[i] = sum;
      }
    }
    std::sort(score_base.begin(), score_base.end());

    auto lt = [&]() {
      std::vector<i64> temp;
      for (const usize i : rep(0, k)) {
        temp.push_back(sum_right[i] + depth_right[i]);
      }
      return segtree(std::move(temp));
    }();
    auto rt = [&]() {
      std::vector<i64> temp;
      for (const usize i : rep(0, k)) {
        temp.push_back(sum_right[i]);
      }
      return segtree(std::move(temp));
    }();

    const auto count_lt = [&](const i64 x) -> u64 {
      u64 ret = 0;
      ret += 1; // all
      if (dsum + depth[all_lca] < x) {
        ret += 1; // none
      }
      ret += std::lower_bound(score_base.begin(), score_base.end(), x) -
        score_base.begin();
      usize bd = k;
      for (const usize i : rep(1, k)) {
        lt.add(sum_right[i] + depth_right[i], 1);
      }
      for (const usize i : rep(0, k - 2)) {
        if (bd != i + 1) {
          lt.add(sum_right[i + 1] + depth_right[i + 1], -1);
        }
        else {
          bd += 1;
          rt.add(sum_right[i + 1], -1);
        }
        while (i + 2 < bd && depth_right[bd - 1] >= depth_left[i]) {
          --bd;
          lt.add(sum_right[bd] + depth_right[bd], -1);
          rt.add(sum_right[bd], 1);
        }
        ret += lt.sum(x - sum_left[i]);
        ret += rt.sum(x - sum_left[i] - depth_left[i]);
      }
      lt.clear();
      rt.clear();
      return ret;
    };

    i64 left = -100000000000001;
    i64 right = -left + 100000;
    const u64 kth = (u64(k) * (k + 1) / 2 + 1 + 1) / 2 - 1;
    count_lt(102);
    while (right - left > 1) {
      const i64 mid = (left + right) / 2;
      if (count_lt(mid) <= kth) {
        left = mid;
      }
      else {
        right = mid;
      }
    }
    std::cout << left << eoln;
  }

} // namespace n91

int main() {
  n91::main_();
  return 0;
}
0