結果

問題 No.900 aδδitivee
ユーザー kimiyukikimiyuki
提出日時 2019-10-05 00:31:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 317 ms / 2,000 ms
コード長 6,512 bytes
コンパイル時間 2,712 ms
コンパイル使用メモリ 224,804 KB
実行使用メモリ 27,584 KB
最終ジャッジ日時 2024-10-03 10:01:44
合計ジャッジ時間 10,115 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 283 ms
22,716 KB
testcase_08 AC 284 ms
22,832 KB
testcase_09 AC 287 ms
22,848 KB
testcase_10 AC 286 ms
22,768 KB
testcase_11 AC 281 ms
22,900 KB
testcase_12 AC 278 ms
22,816 KB
testcase_13 AC 278 ms
22,716 KB
testcase_14 AC 287 ms
22,716 KB
testcase_15 AC 274 ms
22,712 KB
testcase_16 AC 273 ms
22,748 KB
testcase_17 AC 278 ms
22,688 KB
testcase_18 AC 284 ms
22,828 KB
testcase_19 AC 282 ms
22,756 KB
testcase_20 AC 282 ms
22,724 KB
testcase_21 AC 286 ms
22,676 KB
testcase_22 AC 317 ms
27,224 KB
testcase_23 AC 315 ms
27,452 KB
testcase_24 AC 311 ms
27,320 KB
testcase_25 AC 312 ms
27,584 KB
testcase_26 AC 309 ms
27,404 KB
testcase_27 AC 308 ms
27,444 KB
testcase_28 AC 307 ms
27,324 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)
#define dump(x) cerr << #x " = " << x << endl
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, (int)xs.size() - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }

/**
 * @arg g must be a tree
 * @note O(n) time
 * @note O(n) space on heap
 */
struct subtree_info_t {
    int parent;  // in the entire tree
    int depth;  // in the entire tree
    int size;  // of the subtree
    int height;  // of the subtree
};
vector<subtree_info_t> prepare_subtree_info(vector<vector<int> > const & g, int root) {
    int n = g.size();
    vector<subtree_info_t> info(n, (subtree_info_t) { -1, -1, -1, -1 });
    vector<int> topological(n);
    topological[0] = root;
    info[root].parent = root;
    info[root].depth = 0;
    int r = 1;
    for (int l = 0; l < r; ++ l) {
        int i = topological[l];
        for (int j : g[i]) if (j != info[i].parent) {
            topological[r ++] = j;
            info[j].parent = i;
            info[j].depth = info[i].depth + 1;
        }
    }
    while ((-- r) >= 0) {
        int i = topological[r];
        info[i].size = 1;
        info[i].height = 0;
        for (int j : g[i]) if (j != info[i].parent) {
            info[i].size += info[j].size;
            info[i].height = max(info[i].height, info[j].height + 1);
        }
    }
    info[root].parent = -1;
    return info;
}

/**
 * @brief euler tour
 * @arg g must be a tree, directed or undirected
 * @note for constraints, see the unittest
 */
void do_euler_tour(vector<vector<int> > const & g, int root, vector<int> & tour, vector<int> & left, vector<int> & right) {
    int n = g.size();
    tour.clear();
    left.resize(n);
    right.resize(n);
    function<void (int, int)> go = [&](int x, int parent) {
        left[x] = tour.size();
        tour.push_back(x);
        for (int y : g[x]) if (y != parent) {
            go(y, x);
        }
        right[x] = tour.size();
        tour.push_back(x);
    };
    go(root, -1);
}

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef typename OperatorMonoid::value_type operator_type;
    typedef typename OperatorMonoid::target_type value_type;
    int n;
    std::vector<operator_type> f;
    std::vector<value_type> a;
    const OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, value_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n - 1, op.unit());
    }
    value_type point_get(int i) { // 0-based
        value_type acc = a[i];
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i - 1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        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
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i - n + 1] = op.apply(z, a[i - n + 1]);
            }
        } 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.unit();
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
        }
    }
    void point_set(int i, value_type z) {
        range_apply(i, i + 1, op.unit());  // to flush lazed ops
        a[i + n - 1] = z;  // bug??
    }
};

struct add_linear_function_monoid {
    typedef std::pair<int64_t, int64_t> value_type;
    typedef std::pair<int64_t, int64_t> target_type;
    add_linear_function_monoid() = default;
    value_type unit() const {
        return std::make_pair(0, 0);
    }
    value_type append(value_type g, value_type f) const {
        int64_t fst = f.first + g.first;
        int64_t snd = f.second + g.second;
        return std::make_pair(fst, snd);
    }
    target_type apply(value_type f, target_type x) const {
        int64_t fst = f.first + x.first;
        int64_t snd = f.second + x.second;
        return std::make_pair(fst, snd);
    }
};


int main() {
    // input
    int n; cin >> n;
    vector<vector<int> > g(n);
    vector<tuple<int, int, int64_t> > edges;
    REP (i, n - 1) {
        int x, y; int64_t c; cin >> x >> y >> c;
        g[x].push_back(y);
        g[y].push_back(x);
        edges.emplace_back(x, y, c);
    }

    // prepare
    const int root = 0;
    auto info = prepare_subtree_info(g, root);
    vector<int> tour, left, right;
    do_euler_tour(g, root, tour, left, right);
    dual_segment_tree<add_linear_function_monoid> segtree(2 * n, make_pair(0, 0));
    for (auto edge : edges) {
        int x, y; int64_t c; tie(x, y, c) = edge;
        int z = (left[x] <= left[y] and left[y] < right[x] ? y : x);
        segtree.range_apply(left[z], right[z], make_pair(0, c));
    }

    // query
    int q; cin >> q;
    while (q --) {
        int type; cin >> type;
        if (type == 1) {
            int x; int64_t c; cin >> x >> c;
            segtree.range_apply(left[x], right[x], make_pair(c, - c * info[x].depth));
        } else if (type == 2) {
            int y; cin >> y;
            int64_t a, b; tie(a, b) = segtree.point_get(left[y]);
            cout << a * info[y].depth + b << endl;
        }
    }
    return 0;
}
0