Submission #1104931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104931		alexdd	Jobs (BOI24_jobs)	C++17	100 / 100	243 ms	76740 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[300005],parent[300005];
priority_queue<pair<int,int>> pq[300005];//{negativ,profit}
vector<int> con[300005];
void dfs(int nod)
{
    for(int adj:con[nod])
    {
        dfs(adj);
        if((int)pq[nod].size() < (int)pq[adj].size())
            swap(pq[nod], pq[adj]);
        while(!pq[adj].empty())
        {
            pq[nod].push(pq[adj].top());
            pq[adj].pop();
        }
    }
    if(a[nod]>=0)
    {
        pq[nod].push({0,a[nod]});
    }
    else
    {
        pair<int,int> cur = {a[nod],a[nod]};
        while(!pq[nod].empty() && cur.second<0)
        {
            pair<int,int> aux = pq[nod].top();
            pq[nod].pop();
            cur.first = min(cur.first, cur.second + aux.first);
            cur.second += aux.second;
        }
        if(cur.second>=0)
        {
            while(!pq[nod].empty() && pq[nod].top().first >= cur.first)
            {
                cur.second += pq[nod].top().second;
                pq[nod].pop();
            }
            pq[nod].push(cur);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>a[0];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>parent[i];
        con[parent[i]].push_back(i);
    }
    dfs(0);
    int sum=0;
    while(!pq[0].empty() && pq[0].top().first+sum>=0)
    {
        sum += pq[0].top().second;
        pq[0].pop();
    }
    cout<<sum-a[0];
    return 0;
}

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