結果

問題 No.1215 都市消滅ビーム
ユーザー noshi91
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0