Submission #1202047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202047		HasanV11010238	Magic Tree (CEOI19_magictree)	C++20	100 / 100	144 ms	39572 KiB

magictree

#include<bits/stdc++.h>
#define ll long long
#define INF 10000000
#define MAX 1500000
using namespace std;
vector<map<int, ll>> ma;
vector<vector<int>> v, fru;
void dfs(int x){
    for (auto el : v[x]){
        dfs(el);
        if (ma[x].size() < ma[el].size()){
            swap(ma[x], ma[el]);
        }
        for (auto el : ma[el]){
            ma[x][el.first] += el.second;
        }
    }
    if (fru[x][0] != -1){
        ll cw = fru[x][1], ad = fru[x][0];
        ma[x][ad] += cw;
        while (1){
            auto it = ma[x].upper_bound(ad);
            if (it == ma[x].end()) break;
            int tt = it->first;
            if (ma[x][tt] <= cw){
                cw -= it->second;
                ma[x].erase(it);
            }
            else{
                ma[x][tt] -= cw;
                break;
            }
        }
    }
}
int main(){
    int n, m, k, a;
    cin>>n>>m>>k;
    v.assign(n + 1, vector<int>()), ma.assign(n + 1, map<int, ll>()), fru.assign(n + 1, vector<int>(2, 0));
    for (int i = 2; i <= n; i++){
        cin>>a;
        v[a].push_back(i);
    }
    for (int i = 0; i < m; i++){
        cin>>a;
        cin>>fru[a][0]>>fru[a][1];
    }
    dfs(1);
    ll ans = 0;
    for (auto el : ma[1]){
        ans += el.second;
    }
    cout<<ans<<"\n";
}

• 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