Submission #1163822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163822		vladilius	Jobs (BOI24_jobs)	C++20	43 / 100	2102 ms	227120 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e19;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; ll s; cin>>n>>s;
    vector<int> g[n + 1], p(n + 1);
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>p[i];
        g[p[i]].pb(i);
    }
    
    deque<pll> f[n + 1], q;
    function<void(int, int)> dfs = [&](int v, int pr){
        for (int i: g[v]){
            if (i == pr) continue;
            dfs(i, v);
            
            ll x = f[v].empty() ? -inf : f[v].front().ff, y = f[i].empty() ? -inf : f[i].front().ff;
            q.clear();
            while (x != -inf || y != -inf){
                if (x > y){
                    q.push_back(f[v].front());
                    f[v].pop_front();
                    x = f[v].empty() ? -inf : f[v].front().ff;
                }
                else {
                    q.push_back(f[i].front());
                    f[i].pop_front();
                    y = f[i].empty() ? -inf : f[i].front().ff;
                }
            }
            f[v] = q;
        }

        pll p = {a[v], a[v]};
        while (!f[v].empty() && p.ss <= 0){
            auto [x, y] = f[v].front(); f[v].pop_front();
            p.ff = min(p.ff, p.ss + x);
            p.ss += y;
        }
        
        if (p.ss > 0) f[v].push_front(p);
    };
    dfs(0, 0);
    
    ll out = 0;
    while (!f[0].empty()){
        auto [x, y] = f[0].front(); f[0].pop_front();
        if ((s + x) < 0) break;
        s += y; out += y;
    }
    
    cout<<out<<"\n";
}

Compilation message (stderr)

Main.cpp:9:16: warning: overflow in conversion from 'double' to 'll' {aka 'long long int'} changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
    9 | const ll inf = 1e19;
      |                ^~~~

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