結果

問題 No.899 γatheree
ユーザー kimiyukikimiyuki
提出日時 2019-10-04 22:19:20
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 751 ms / 2,000 ms
コード長 7,270 bytes
コンパイル時間 2,697 ms
コンパイル使用メモリ 215,884 KB
実行使用メモリ 15,876 KB
最終ジャッジ日時 2024-04-14 11:03:53
合計ジャッジ時間 17,926 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 736 ms
15,740 KB
testcase_07 AC 731 ms
15,744 KB
testcase_08 AC 730 ms
15,604 KB
testcase_09 AC 740 ms
15,628 KB
testcase_10 AC 743 ms
15,608 KB
testcase_11 AC 738 ms
15,536 KB
testcase_12 AC 731 ms
15,624 KB
testcase_13 AC 751 ms
15,604 KB
testcase_14 AC 747 ms
15,608 KB
testcase_15 AC 743 ms
15,744 KB
testcase_16 AC 746 ms
15,748 KB
testcase_17 AC 747 ms
15,620 KB
testcase_18 AC 744 ms
15,612 KB
testcase_19 AC 751 ms
15,748 KB
testcase_20 AC 748 ms
15,876 KB
testcase_21 AC 720 ms
15,876 KB
testcase_22 AC 707 ms
15,872 KB
testcase_23 AC 709 ms
15,872 KB
権限があれば一括ダウンロードができます

ソースコード

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