Submission #1361902

#TimeUsernameProblemLanguageResultExecution timeMemory
1361902vlad7654Magic Tree (CEOI19_magictree)C++20
100 / 100
154 ms34056 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> graph;
vector<int> weight, day;
map<int,int>* dfs(int node, int parent=-1) {
    map<int,int> *cur = new map<int,int>();
    (*cur)[day[node]]+=weight[node];
    for (auto it:graph[node]) {
        if (it==parent) continue;
        auto temp=dfs(it,node);
        if (cur->size()<temp->size()) swap(cur,temp);
        for (auto &[d, w]:(*temp)) {
            (*cur)[d]+=w;
        }
        delete temp;
    }

    vector<int> to_remove;
    for (auto it=next(cur->find(day[node]));it!=cur->end();it=next(it)) {
        if (it->second>=weight[node]) {
            it->second-=weight[node];
            break;
        }
        to_remove.push_back(it->first);
        weight[node]-=it->second;
    }
    for (auto it:to_remove) {
        cur->erase(it);
    }

    return cur;

}
signed main() {
    int n, m, k;
    cin >> n >> m >> k;
    graph.resize(n+1);
    weight.resize(n+1);
    day.resize(n+1);
    for (int i=2;i<=n;i++) {
        int p;
        cin>>p;
        graph[i].push_back(p);
        graph[p].push_back(i);
    }
    for (int i=1;i<=m;i++) {
        int u, d, w;
        cin>>u>>d>>w;
        weight[u]=w;
        day[u]=d;
    }
    int cnt=0;
    auto ans=dfs(1);
    for (auto it:*ans) {
        cnt+=it.second;
    }
    cout<<cnt;
}
#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...