結果
問題 | No.1215 都市消滅ビーム |
ユーザー |
![]() |
提出日時 | 2020-08-30 16:32:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,195 ms / 6,000 ms |
コード長 | 9,432 bytes |
コンパイル時間 | 2,769 ms |
コンパイル使用メモリ | 100,364 KB |
最終ジャッジ日時 | 2025-01-14 00:02:14 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
//#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_templatenamespace 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]);{// leftdepth_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;}}{// rightdepth_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; // allif (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 n91int main() {n91::main_();return 0;}