Submission #591430

#	Time	Username	Problem	Language	Result	Execution time	Memory
591430		alextodoran	Magic Tree (CEOI19_magictree)	C++17	100 / 100	469 ms	71276 KiB

magictree

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int K_MAX = 100000;

int N, M, K;
int parent[N_MAX + 2];
vector <int> sons[N_MAX + 2];

int ripeTime[N_MAX + 2];
ll juice[N_MAX + 2];

struct Fenwick {
    map <int, ll> mp;
    map <int, ll> upds;
    void update (int pos, ll val) {
        upds[pos] += val;
        for (int i = pos; i <= K; i += i & -i) {
            mp[i] += val;
        }
    }
    ll query (int pos) {
        ll val = 0;
        for (int i = pos; i >= 1; i -= i & -i) {
            if (mp.find(i) != mp.end()) {
                val += mp[i];
            }
        }
        return val;
    }
    void maxify (int pos, ll val) {
        update(pos, val);
        while (val > 0) {
            map <int, ll> :: iterator it = upds.lower_bound(pos + 1);
            if (it == upds.end()) {
                break;
            }
            int itpos = it->first;
            ll itval = it->second;
            if (itval <= val) {
                update(itpos, -itval);
                val -= itval;
                upds.erase(itpos);
            } else {
                update(itpos, -val);
                val = 0;
            }
        }
    }
};

Fenwick Fen[K_MAX + 2];

void dfs (int u) {
    int heavy = -1;
    for (int v : sons[u]) {
        dfs(v);
        if (heavy == -1 || (int) Fen[heavy].upds.size() < (int) Fen[v].upds.size()) {
            heavy = v;
        }
    }
    if (heavy != -1) {
        swap(Fen[u], Fen[heavy]);
    }
    for (int v : sons[u]) {
        if (v != heavy) {
            for (pair <int, ll> upd : Fen[v].upds) {
                Fen[u].update(upd.first, upd.second);
            }
            Fen[v].upds.clear();
            Fen[v].mp.clear();
        }
    }
    if (juice[u] != 0) {
        Fen[u].maxify(ripeTime[u], juice[u]);
    }
}

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

    cin >> N >> M >> K;
    for (int u = 2; u <= N; u++) {
        cin >> parent[u];
        sons[parent[u]].push_back(u);
    }
    for (int i = 1; i <= M; i++) {
        int u;
        cin >> u;
        cin >> ripeTime[u] >> juice[u];
    }

    dfs(1);
    cout << Fen[1].query(K) << "\n";

    return 0;
}

• 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