結果

問題 No.899 γatheree
ユーザー kimiyukikimiyuki
提出日時 2019-10-04 22:19:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 859 ms / 2,000 ms
コード長 7,270 bytes
コンパイル時間 2,813 ms
コンパイル使用メモリ 211,928 KB
最終ジャッジ日時 2025-01-07 20:38:10
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
/**
* @note lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> is the starry sky tree
* @note verified https://www.hackerrank.com/contests/world-codesprint-12/challenges/factorial-array/submissions/code/1304452669
* @note verified https://www.hackerrank.com/contests/world-codesprint-12/challenges/animal-transport/submissions/code/1304454860
* @note intersting discussion about range-extension and partial-function-extension: https://github.com/kmyk/competitive-programming-library/issues/3
*/
template <class Monoid, class OperatorMonoid>
struct lazy_propagation_segment_tree { // on monoids
static_assert (std::is_same<typename Monoid::value_type, typename OperatorMonoid::target_type>::value, "");
typedef typename Monoid::value_type value_type;
typedef typename OperatorMonoid::value_type operator_type;
const Monoid mon;
const OperatorMonoid op;
int n;
std::vector<value_type> a;
std::vector<operator_type> f;
lazy_propagation_segment_tree() = default;
lazy_propagation_segment_tree(int a_n, value_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op =
        OperatorMonoid())
: mon(a_mon), op(a_op) {
n = 1; while (n <= a_n) n *= 2;
a.resize(2 * n - 1, mon.unit());
std::fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
f.resize(std::max(0, (2 * n - 1) - n), op.identity());
}
void point_set(int i, value_type z) {
assert (0 <= i and i < n);
point_set(0, 0, n, i, z);
}
void point_set(int i, int il, int ir, int j, value_type z) {
if (i == n + j - 1) { // 0-based
a[i] = z;
} else if (ir <= j or j+1 <= il) {
// nop
} else {
range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
f[i] = op.identity();
point_set(2 * i + 1, il, (il + ir) / 2, j, z);
point_set(2 * i + 2, (il + ir) / 2, ir, j, z);
a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
}
}
void range_apply(int l, int r, operator_type z) {
assert (0 <= l and l <= r and r <= n);
range_apply(0, 0, n, l, r, z);
}
void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
if (l <= il and ir <= r) { // 0-based
a[i] = op.apply(z, a[i]);
if (i < f.size()) f[i] = op.compose(z, f[i]);
} else if (ir <= l or r <= il) {
// nop
} else {
range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
f[i] = op.identity(); // unnecessary if the oprator monoid is commutative
range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
}
}
value_type range_concat(int l, int r) {
assert (0 <= l and l <= r and r <= n);
value_type lacc = mon.unit(), racc = mon.unit();
for (int l1 = (l += n), r1 = (r += n) - 1; l1 > 1; l /= 2, r /= 2, l1 /= 2, r1 /= 2) { // 1-based loop, 2x faster than recursion
if (l < r) {
if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
}
lacc = op.apply(f[l1 / 2 - 1], lacc);
racc = op.apply(f[r1 / 2 - 1], racc);
}
return mon.append(lacc, racc);
}
};
struct plus_monoid {
typedef int64_t value_type;
int64_t unit() const { return 0; }
int64_t append(int64_t a, int64_t b) const { return a + b; }
};
struct const_operator_monoid {
typedef int64_t value_type;
typedef int64_t target_type;
int64_t identity() const { return INT64_MIN; } // a dummy value
int64_t apply(value_type a, target_type b) const { return a == INT64_MIN ? b : a; }
int64_t compose(value_type a, value_type b) const { return a == INT64_MIN ? b : a; }
};
/**
* @brief something like euler tour but do BFS
* @arg g must be a tree, directed or undirected
* @note for constraints, see the unittest
* @arg parent is initialized
* @arg left and
* @arg right are the ranges of descendants of k-th level
* @note O(N * DEPTH)
* @sa https://yukicoder.me/problems/no/899
*/
template <int DEPTH>
void do_bfs_tour(vector<vector<int> > const & g, int root, vector<int> & tour, vector<int> & parent, vector<array<int, DEPTH> > & left, vector<array
    <int, DEPTH> > & right) {
int n = g.size();
tour.clear();
parent.assign(n, -1);
left.resize(n);
right.resize(n);
queue<int> que;
que.push(root);
while (not que.empty()) {
int x = que.front();
que.pop();
int i = tour.size();
// initialize current
tour.push_back(x);
fill(ALL(left[x]), n);
fill(ALL(right[x]), n);
// update parent
int y = x;
REP (d, DEPTH) {
y = parent[y];
if (y == -1) break;
left[y][d] = min(left[y][d], i);
right[y][d] = i + 1;
}
// go children
for (int y : g[x]) if (y != parent[x]) {
parent[y] = x;
que.push(y);
}
}
}
int main() {
// input the initial state
int n; cin >> n;
vector<vector<int> > g(n);
REP (i, n - 1) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int64_t> a(n);
REP (i, n) {
cin >> a[i];
}
// prepare
const int root = 0;
vector<int> tour, parent;
vector<array<int, 2> > left, right;
do_bfs_tour<2>(g, root, tour, parent, left, right);
vector<int> lookup(n);
REP (i, n) {
lookup[tour[i]] = i;
}
lazy_propagation_segment_tree<plus_monoid, const_operator_monoid> segtree(n);
REP (x, n) {
segtree.point_set(lookup[x], a[x]);
}
// query
int q; cin >> q;
while (q --) {
int x; cin >> x;
int64_t acc = 0;
auto f = [&](int l, int r) {
acc += segtree.range_concat(l, r);
segtree.range_apply(l, r, 0);
};
f(left[x][1], right[x][1]);
f(left[x][0], right[x][0]);
if (x == root) {
f(lookup[x], lookup[x] + 1);
} else {
f(left[parent[x]][0], right[parent[x]][0]);
f(lookup[parent[x]], lookup[parent[x]] + 1);
if (parent[x] != root) {
f(lookup[parent[parent[x]]], lookup[parent[parent[x]]] + 1);
}
}
segtree.point_set(lookup[x], acc);
cout << acc << endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0