#386897 (C++17) No.900 aδδitivee

• 問題: No.900 aδδitivee
• ユーザー: kimiyuki
• 提出日時: 2019-10-04 23:19:45
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,500 bytes
• コンパイル時間: 2,383 ms
• コンパイル使用メモリ: 216,180 KB
• 最終ジャッジ日時: 2025-01-07 20:50:48
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	WA * 2
other	WA * 27

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#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] <= y and 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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX