Submission #1192984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192984		thangdz2k7	Magic Tree (CEOI19_magictree)	C++17	100 / 100	232 ms	29412 KiB

magictree

#include <bits/stdc++.h>

using namespace std;
using vi = vector <int>;

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
    static_assert(D >= 1, "Dimension must be positive");
    template <typename... Args>
    Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
    Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

long long solve(int N, int M, int K, vi P, vi V, vi D, vi W){
    vector <vi> adj(N);
    for (int i = 1; i < N; ++ i)
        adj[P[i]].push_back(i);

    vi t_in(N), t_out(N), mxj(N, 0);
    int timer = -1;

    int LG = log2(N - 1);
    Vec <2, int> to(N, LG + 1, -1);

    function <void(int)> dfs = [&](int u) {

        t_in[u] = ++ timer;

        for (int i = 1; i <= LG; ++ i){
            int v = to[u][i - 1];
            if (v < 0) break;
            to[u][i] = to[v][i - 1];
            mxj[u] = i + 1;
        }

        for (int v : adj[u])
            to[v][0] = u, dfs(v);

        t_out[u] = timer;

    }; dfs(0);

    vector <int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int u, int v) {
        if (D[u] != D[v]) return D[u] < D[v];
        return t_in[V[u]] > t_in[V[v]];
    });

    vector <long long> bit(N + 1, 0);

    auto update = [&](int l, int r, int val) -> void {
        for (l = l + 1; l <= N; l += l & -l)
            bit[l] += val;
        for (r = r + 2; r <= N; r += r & -r)
            bit[r] -= val;
    };

    auto get = [&](int p) -> long long {
        long long rt = 0;
        for (p = p + 1; p; p -= p & -p)
            rt += bit[p];

        return rt;
    };

    long long ans = 0;

    for (int i : ord){
        ans += W[i];
        long long need = W[i];
        int u = V[i];
        update(t_in[u], t_out[u], W[i]);

        while (get(t_in[P[u]]) > 0){
            u = P[u];
            long long tmp = get(t_in[u]);

            for (int l = mxj[u] - 1; l >= 0; -- l)
                if (to[u][l] > -1 && get(t_in[to[u][l]]) == tmp)
                    u = to[u][l];

            long long cur = get(t_in[u]) - get(t_in[P[u]]);
            if (cur >= need){
                ans -= need;
                update(t_in[u], t_out[u], -need);
                break;
            }
            ans -= cur;
            update(t_in[u], t_out[u], -cur);
            need -= cur;
        }
    }

    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, k; cin >> n >> m >> k;
    vi p(n, -1), v(m), d(m), w(m);
    for (int i = 1; i < n; ++ i){
        cin >> p[i];
        p[i] --;
    }
    for (int i = 0; i < m; ++ i){
        cin >> v[i] >> d[i] >> w[i];
        v[i] --;
    }

    cout << solve(n, m, k, p, v, d, w);
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17