Submission #1361553

#TimeUsernameProblemLanguageResultExecution timeMemory
1361553po_rag526Magic Tree (CEOI19_magictree)C++20
3 / 100
588 ms37476 KiB
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
//#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
#define all(x) (x).begin(), (x).end()
const ll mod7 = 1e9+7, mod9= 998244353, MAX_N = 10000000;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> child[112345];
ll D[112345], W[112345];

map<ll,ll> *dfs(ll i) {
    map<ll,ll> *big = new map<ll,ll>();
    for (auto j : child[i]) {
        auto sm = dfs(j);
        if (big -> size() < sm -> size()) {
            swap(big, sm);
        }
        for (auto k : *sm) {
            (*big)[k.pF] += k.pS;
        }
    }
    if (D[i] != -1) {
        (*big)[D[i]] += W[i];

        auto it = (big -> find(D[i]));
        auto itnext = next(it);
        while (itnext != big -> end() && W[i] > 0) {
            if (W[i] >= itnext -> pS) {
                W[i] -= itnext -> pS;
                big -> erase(itnext);
            }
            else {
                itnext -> pS -= W[i];
            }
            itnext = next(it);
        }
    }
    return big;
}
int main() {
    ll n, m, k; cin>>n>>m>>k;
    for (int i=2; i<=n; i++) {
        ll u; cin>>u;
        child[u].pb(i);
    }
    for (int i=1; i<=n; i++) D[i] = W[i] = -1;
    while (m--) {
        ll v, d, w; cin>>v>>d>>w;
        D[v] = d;
        W[v] = w;
    }
    map<ll,ll> *diffArr = dfs(1);
    ll sum = 0;
    for (auto i : *diffArr) {
        sum += i.pS;
    }
    cout << sum << endl;
}
#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...