Submission #1131853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131853		shjeong	Jobs (BOI24_jobs)	C++20	100 / 100	204 ms	83644 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define sz(x) (ll)x.size()
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> PP;
const ll Lnf = 2e18;
const ll inf = 1e9;
ll n;
ll num[303030];
priority_queue<pi> pq[303030];
ll p[303030], w[303030];
vector<ll> adj[303030];
void dfs(ll x){
    for(auto next : adj[x]){
        dfs(next);
        if(sz(pq[num[next]]) > sz(pq[num[x]]))swap(num[x],num[next]);
        while(sz(pq[num[next]])){
            auto t = pq[num[next]].top(); pq[num[next]].pop(); pq[num[x]].push(t);
        }
    }
    if(w[x]>0)pq[num[x]].push({0,w[x]});
    else{
        ll l, g; l=g=w[x];
        auto &t = pq[num[x]];
        while(sz(t)){
            auto [L, G] = t.top(); if(g>0 and L<l)break; t.pop();
            if(g<=0)l = min(l,g+L);  //loss
            g += G;
        }
        if(g>0)pq[num[x]].push({l,g});
    }
}
int main(){
    fast;
    cin>>n>>w[0];
    for(int i = 1 ; i <= n ; i++)num[i]=i,cin>>w[i]>>p[i], adj[p[i]].push_back(i);
    dfs(0);
    ll ans = 0;
    auto &t = pq[num[0]];
    while(sz(t)){
        auto [x,y] = t.top(); t.pop(); if(ans+x>=0)ans+=y; else break;
    }
    cout<<ans-w[0];
}

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