Submission #1253865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253865		skibidihehe	Jobs (BOI24_jobs)	C++20	0 / 100	353 ms	37468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define taskname ""
#define ld long double

int N;
ll s;
vector<ll> x;
vector<vector<int>> ch;

// returns {pointer to multiset of kept profits, sum_of_that_multiset}
pair<multiset<ll>*, ll> dfs(int u){
    // start with an empty multiset at u
    auto *ms = new multiset<ll>();
    ll sum = 0;
    // merge children’s sets into ours
    for(int v : ch[u]){
        auto [cs, csum] = dfs(v);
        // small-to-large: ensure *ms is the larger
        if(ms->size() < cs->size()){
            swap(ms, cs);
            swap(sum, csum);
        }
        // merge cs into ms
        for(ll val : *cs){
            ms->insert(val);
        }
        sum += csum;
        delete cs;
    }
    // insert u’s own profit
    ms->insert(x[u]);
    sum += x[u];
    // if we go negative, keep dropping the smallest until sum ≥ 0
    while(sum < 0){
        auto it = ms->begin();  // worst loss
        sum -= *it;
        ms->erase(it);
    }
    return {ms, sum};
}

int main(){
    if(fopen(taskname".inp","r")){
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> s;
    x.assign(N+1, 0);
    ch.assign(N+1, {});

    // dummy root 0 holds your initial capital
    x[0] = s;

    for(int i = 1; i <= N; i++){
        int p;
        cin >> x[i] >> p;
        ch[p].pb(i);
    }

    auto [rootSet, rootSum] = dfs(0);
    // rootSum = s + sum(chosen real x[i]); so subtract s
    ll answer = rootSum - s;
    cout << answer;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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