Submission #1361555

#TimeUsernameProblemLanguageResultExecution timeMemory
1361555domiMagic Tree (CEOI19_magictree)C++20
100 / 100
72 ms41644 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e5;

using namespace std;

using DS = map<int, int>;

vector<int> T[NMAX + 5];
vector<int> to_remove;
int d[NMAX + 5], w[NMAX + 5], par[NMAX + 5], n, m, k;

DS* dfs(int nod, int p = -1) {
    auto cur = new DS();

    for (auto &son : T[nod]) {
        if (son == p) continue;

        auto fiu = dfs(son, nod);
        if (cur->size() < fiu->size()) swap(cur, fiu);
        for (auto &[day, val] : (*fiu)) {
            (*cur)[day] += val;
        }

        //delete fiu;
    }

    (*cur)[d[nod]] += w[nod];
    to_remove.clear();
    for (auto it = next(cur->find(d[nod])); it != cur->end(); it = next(it)) {
        auto &[day, val] = (*it);
        if (val > w[nod]) {
            val -= w[nod];
            break;
        }

        w[nod] -= val;
        to_remove.push_back(day);
    }

    for (auto &day : to_remove)
        cur->erase(day);

    return cur;
}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;

    for (int i = 2; i <= n; ++i) {
        cin >> par[i];
        T[i].push_back(par[i]);
        T[par[i]].push_back(i);
    }
    for(int i=1; i<= m; ++i) {
        int u, weight, day;
        cin >> u >> day >> weight;
        w[u]=weight;
        d[u]=day;
    }
    auto root = dfs(1);
    int ans = 0;
    for (auto &[day, val] : (*root)) {
        if (day > k) continue;
        ans += val;
    }

    cout << ans << '\n';
    return 0;
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...