Submission #1194270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194270		Unforgettablepl	Jobs (BOI24_jobs)	C++20	100 / 100	238 ms	89672 KiB

Main

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

#define int long long

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,s;
    cin >> N >> s;
    int back = s;
    vector<vector<int>> adj(N+1);
    vector<int> cost(N+1);
    for(int i=1;i<=N;i++){
        int p;
        cin >> cost[i] >> p;
        adj[p].emplace_back(i);
    }
    auto add = [&](pair<int,map<int,int>> &a,pair<int,map<int,int>> &b){
        if(a.second.size()<b.second.size())swap(a,b);
        for(auto&[x,y]:b.second){
            a.second[x-b.first+a.first]+=y;
        }
    };
    function<pair<int,map<int,int>>(int)> dfs = [&](int x){
        pair<int,map<int,int>> curr = {0,{}};
        if(cost[x]>=0){curr.second[0]=cost[x];}
        for(int&i:adj[x]){
            auto t = dfs(i);
            add(curr,t);
        }
        if(cost[x]<0){
            cost[x] = -cost[x];
            while(!curr.second.empty()){
                int trans = min(cost[x],curr.second.begin()->second);
                auto iter = ++curr.second.begin();
                if(iter!=curr.second.end()){
                    trans = min(trans,(iter->first)-(curr.second.begin()->first));
                }
                cost[x]-=trans;
                if(curr.second.begin()->second-trans != 0)curr.second[(curr.second.begin()->first)+trans]+=(curr.second.begin()->second)-trans;
                curr.second.erase(curr.second.begin());
                if(cost[x]==0)break;
            }
        }
        return curr;
    };
    auto t = dfs(0);
    while(!t.second.empty() and t.second.begin()->first<=s+t.first){
        s+=t.second.begin()->second;
        t.second.erase(t.second.begin());
    }
    cout << s-back << '\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31