Submission #1124267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124267		MateiKing80	Jobs (BOI24_jobs)	C++20	100 / 100	266 ms	67260 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 3e5;

int n;
int a[N + 5], parent[N + 5];

priority_queue<pair<int,int>> pq[N + 5];
vector<int> con[N + 5];

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];
}

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