結果

問題 No.1215 都市消滅ビーム
ユーザー yosupot
提出日時 2020-08-30 18:15:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,794 ms / 6,000 ms
コード長 13,019 bytes
コンパイル時間 4,933 ms
コンパイル使用メモリ 151,396 KB
最終ジャッジ日時 2025-01-14 02:01:40
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#include <unistd.h>
struct Scanner {
int fd = -1;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += ::read(fd, line + ed, (1 << 15) - ed);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
bool read_single(T& ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) {
ref = 10 * ref + (line[st++] & 0xf);
}
if (neg) ref = -ref;
return true;
}
template <class T> bool read_single(V<T>& ref) {
for (auto& d : ref) {
if (!read_single(d)) return false;
}
return true;
}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
Scanner(FILE* fp) : fd(fileno(fp)) {}
};
struct Printer {
public:
template <bool F = false> void write() {}
template <bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(' ');
write_single(h);
write<true>(t...);
}
template <class... T> void writeln(const T&... t) {
write(t...);
write_single('\n');
}
Printer(FILE* _fp) : fp(_fp) {}
~Printer() { flush(); }
private:
static constexpr size_t SIZE = 1 << 15;
FILE* fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write_single(const char& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
void write_single(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) {
line[pos + i] = small[len - 1 - i];
}
pos += len;
}
void write_single(__int128 val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) {
line[pos + i] = small[len - 1 - i];
}
pos += len;
}
void write_single(const string& s) {
for (char c : s) write_single(c);
}
void write_single(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write_single(s[i]);
}
template <class T> void write_single(const V<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
struct LCA {
int lg;
VV<int> anc;
V<int> dps;
/// lrLCA
int query(int l, int r) {
if (dps[l] < dps[r]) swap(l, r);
int dd = dps[l] - dps[r];
for (int i = lg - 1; i >= 0; i--) {
if (dd < (1 << i)) continue;
dd -= 1 << i;
l = anc[i][l];
}
if (l == r) return l;
for (int i = lg - 1; i >= 0; i--) {
if (anc[i][l] == anc[i][r]) continue;
tie(l, r) = tie(anc[i][l], anc[i][r]);
}
return anc[0][l];
}
int up(int p, int dist) {
for (int i = lg - 1; i >= 0; i--) {
if (dist >= (1 << i)) {
dist -= 1 << i;
p = anc[i][p];
}
}
return p;
}
int dist(int l, int r) {
int z = query(l, r);
return dps[l] + dps[r] - 2 * dps[z];
}
};
template <class E> struct LCAExec : LCA {
const VV<E>& g;
/// rrootid
LCAExec(const VV<E>& _g, int r) : g(_g) {
int N = int(g.size());
lg = 1;
while ((1 << lg) < N) lg++;
anc = VV<int>(lg, V<int>(N, -1));
dps = V<int>(N);
dfs(r, -1, 0);
for (int i = 1; i < lg; i++) {
for (int j = 0; j < N; j++) {
anc[i][j] =
(anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
}
}
}
void dfs(int p, int b, int now) {
anc[0][p] = b;
dps[p] = now;
for (E e : g[p]) {
if (e.to == b) continue;
dfs(e.to, p, now + 1);
}
}
};
template <class E> LCA get_lca(const VV<E>& g, int r) {
return LCAExec<E>(g, r);
}
// wavelet matrix
struct Wavelet {
// space: 32N bits
struct BitVector {
V<int> _rank = {0};
BitVector(V<char> v = V<char>()) {
_rank.reserve(v.size() + 1);
for (int d : v) _rank.push_back(_rank.back() + d);
}
int rank(bool f, int k) { return f ? _rank[k] : (k - _rank[k]); }
int rank(bool f, int l, int r) { return rank(f, r) - rank(f, l); }
};
// space: 1.5N bits
/*struct BitVector {
V<ull> v;
V<int> _rank;
BitVector(V<char> _v = V<char>()) {
int n = int(_v.size());
v = V<ull>((n + 63) / 64);
_rank = V<int>(v.size() + 1);
for (int i = 0; i < n; i++) {
if (_v[i]) {
v[i / 64] |= 1ULL << (i % 64);
_rank[i / 64 + 1]++;
}
}
for (int i = 0; i < int(v.size()); i++) {
_rank[i+1] += _rank[i];
}
}
int rank(int k) {
int a = _rank[k / 64];
if (k % 64) a += __builtin_popcountll(v[k / 64] << (64 - k % 64));
return a;
}
int rank(bool f, int k) { return f ? rank(k) : k - rank(k); }
int rank(bool f, int l, int r) { return rank(f, r) - rank(f, l); }
};*/
int n, lg = 1;
V<int> mid;
V<BitVector> data;
Wavelet(V<int> v = V<int>()) : n(int(v.size())) {
int ma = 0;
for (int x : v) ma = max(ma, x);
while ((1 << lg) <= ma) lg++;
mid = V<int>(lg);
data = V<BitVector>(lg);
for (int lv = lg - 1; lv >= 0; lv--) {
V<char> buf;
VV<int> nx(2);
for (int d : v) {
bool f = (d & (1 << lv)) > 0;
buf.push_back(f);
nx[f].push_back(d);
}
mid[lv] = int(nx[0].size());
data[lv] = BitVector(buf);
v.clear();
v.insert(v.end(), nx[0].begin(), nx[0].end());
v.insert(v.end(), nx[1].begin(), nx[1].end());
}
}
pair<int, int> succ(bool f, int a, int b, int lv) {
int na = data[lv].rank(f, a) + (f ? mid[lv] : 0);
int nb = data[lv].rank(f, b) + (f ? mid[lv] : 0);
return make_pair(na, nb);
}
// count i, s.t. (a <= i < b) && (v[i] < u)
int rank(int a, int b, int u) {
if ((1 << lg) <= u) return b - a;
int ans = 0;
for (int lv = lg - 1; lv >= 0; lv--) {
bool f = (u & (1 << lv)) > 0;
if (f) ans += data[lv].rank(false, a, b);
tie(a, b) = succ(f, a, b, lv);
}
return ans;
}
// k-th(0-indexed!) number in v[a..b]
int select(int a, int b, int k) {
int u = 0;
for (int lv = lg - 1; lv >= 0; lv--) {
int le = data[lv].rank(false, a, b);
bool f = (le <= k);
if (f) {
u += (1 << lv);
k -= le;
}
tie(a, b) = succ(f, a, b, lv);
}
return u;
}
};
struct CompressWavelet {
Wavelet wt;
V<ll> v, vidx;
int zip(ll x) {
return int(lower_bound(vidx.begin(), vidx.end(), x) - vidx.begin());
}
CompressWavelet(V<ll> _v = V<ll>()) : v(_v), vidx(v) {
sort(vidx.begin(), vidx.end());
vidx.erase(unique(vidx.begin(), vidx.end()), vidx.end());
V<int> v2;
for (auto d: v) v2.push_back(zip(d));
wt = Wavelet(v2);
}
int rank(int a, int b, ll u) { return wt.rank(a, b, zip(u)); }
};
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
int main() {
int n, k;
sc.read(n, k);
V<int> c(k);
V<ll> d(k);
for (int i = 0; i < k; i++) {
sc.read(c[i]);
c[i]--;
}
for (int i = 0; i < k; i++) {
sc.read(d[i]);
}
struct E { int to; };
VV<E> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
sc.read(u, v); u--; v--;
g[u].push_back({v});
g[v].push_back({u});
}
auto lca = get_lca(g, 0);
int mid = lca.dps[lca.query(c[0], c[k - 1])];
V<ll> spe;
V<ll> ls(k), rs(k);
V<int> lh(k), rh(k);
{
int pos = -1;
for (int i = 0; i < k; i++) {
pos = (pos == -1 ? c[i] : lca.query(pos, c[i]));
ls[i] = d[i];
if (i) ls[i] += ls[i - 1];
lh[i] = lca.dps[pos];
spe.push_back(ls[i] + lh[i]);
lh[i] = min(lh[i], mid);
}
}
{
int pos = -1;
for (int i = k - 1; i >= 0; i--) {
pos = (pos == -1 ? c[i] : lca.query(pos, c[i]));
rs[i] = d[i];
if (i + 1 < k) rs[i] += rs[i + 1];
rh[i] = lca.dps[pos];
if (i) spe.push_back(rs[i] + rh[i]);
rh[i] = min(rh[i], mid);
}
}
;
;
CompressWavelet lwt(ls), rwt(rs);
// x
auto solve = [&](ll x) {
ll ans = 1; // -10^10^10
for (ll y: spe) {
if (y <= x) ans++;
}
{
// lh <= rh
int j = k - 1;
for (int i = 0; i < k - 2; i++) {
j = max(j, i + 1);
while (i + 1 < j && lh[i] <= rh[j]) j--;
// rs[j] + ls[i] + lh[i] <= x
ans += rwt.rank(j + 1, k, x - ls[i] - lh[i] + 1);
}
}
{
// lh > rh
int j = 0;
for (int i = k - 1; i >= 2; i--) {
j = min(j, i - 1);
while (j < i - 1 && lh[j] > rh[i]) j++;
ans += lwt.rank(0, j, x - rs[i] - rh[i] + 1);
}
}
;
return ans;
};
ll alc = ll(k) * (k + 1) / 2 + 1;
;
ll lw = -TEN(15), up = TEN(15);
;
while (up - lw > 1) {
ll md = (lw + up) / 2;
if (solve(md) < (alc + 1) / 2) {
lw = md;
} else {
up = md;
}
}
pr.writeln(up);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0