Submission #1279679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279679		DanielPr8	Magic Tree (CEOI19_magictree)	C++20	100 / 100	115 ms	39796 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()


void merge(multiset<pll>& a, multiset<pll>& b){
    if(a.size()<b.size())swap(a,b);
    for(auto [d,w]:b){
        a.insert({d,w});
    }
}
void pl(multiset<pll>& a, ll d, ll w){
    a.insert({d,w});
    while(w>0){
        auto it = a.upper_bound({d,1e18});
        if(it==a.end())break;
        w-=(*it).s;
        ll las = (*it).f;
        a.erase(it);
        if(w<0){
            a.insert({las, -w});
            w=0;
        }
    }
}
vvl g;
vll d, w;
vector<multiset<pll>> he;
ll k;
void dfs(ll cur){
    for(ll i:g[cur]){
        dfs(i);
        merge(he[cur], he[i]);
    }
    if(d[cur]!=-1)pl(he[cur], d[cur], w[cur]);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, m;
    cin >> n >> m >> k;
    g = vvl(n);
    he = vector<multiset<pll>>(n);
    d = w = vll(n, -1);
    for(ll p,i = 1; i < n; ++i){
        cin >> p;
        p--;
        g[p].pb(i);
    }
    for(ll a,b,c,i = 0; i < m; ++i){
        cin >> a >> b >> c;
        a--;
        d[a]=b;
        w[a]=c;
    }
    dfs(0);
    ll ans = 0;
    for(auto i:he[0])ans += i.s;
    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