Submission #949516

#	Time	Username	Problem	Language	Result	Execution time	Memory
949516		berr	Magic Tree (CEOI19_magictree)	C++17	100 / 100	129 ms	35676 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define int long long


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

    int n, m, k; cin >> n >> m >> k;

    vector<vector<int>> g(n);
    array<int, 2> base = {-1, -1};
    vector<array<int, 2>> val(n, base);
    
    for(int i=1; i<n; i++){
        int x; cin >> x; x--;
        g[x].push_back(i);
    }

    for(int i=0; i<m; i++){
        int v, d, w; cin >> v >> d >> w;
        v--;
        val[v] = {d, w};
    }

    auto dfs=[&](int v, auto&&dfs)->set<array<int, 2>>{
        set<array<int, 2>> res;
        res.insert({0, 0});

        for(auto i: g[v]){
            auto x = dfs(i, dfs);
            if(x.size() > res.size()) swap(res, x);
        
            for(auto i: x){
                auto a = res.lower_bound({i[0], 0});

                if(a==res.end()||(*a)[0] > i[0]) a=prev(a);
                if((*a)[0] == i[0]){
                    i[1]+=(*a)[1];
                    res.erase(a);
                    res.insert(i); 
                 
                }
                else{
                    
                    res.insert(i);
            
                }
            }
        }

        
        if(val[v][0]!=-1){
            auto a = res.lower_bound({val[v][0], 0});
            auto i=val[v];

            if(a==res.end()||(*a)[0] > i[0]) a=prev(a);
            if((*a)[0] == i[0]){
                i[1]+=(*a)[1];
                res.erase(a);
                res.insert(i);
            
            }
            else{
                
                res.insert(i);
            }
            auto it = res.upper_bound({val[v][0], (int)1e18});

            while(it!=res.end()){
               
                    if((*it)[1]>val[v][1]){
                        array<int, 2> x=*it;
                        res.erase(it);
                        x[1]-=val[v][1];
                        if(x[1]) res.insert(x);
                        break;
                    } 
                    else{
                        val[v][1]-=(*it)[1];
                        it = res.erase(it);
                    }
                
            }
        }

        return res;
    };

    auto x = dfs(0, dfs);
    int ans=0;
    for(auto i: x)ans+=i[1];

    cout<<ans;

}   

• 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