結果
問題 | No.1215 都市消滅ビーム |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
//#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;/// lとrの頂点のLCAを求める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;/// 事前処理を行う rはroot頂点のidLCAExec(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 matrixstruct Wavelet {// space: 32N bitsstruct 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^10for (ll y: spe) {if (y <= x) ans++;}{// lh <= rhint 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] <= xans += rwt.rank(j + 1, k, x - ls[i] - lh[i] + 1);}}{// lh > rhint 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;}