Submission #995533

#	Time	Username	Problem	Language	Result	Execution time	Memory
995533		12345678	Jobs (BOI24_jobs)	C++17	29 / 100	124 ms	32768 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, s, vs[nx], c[nx], p, res, cur;
vector<ll> d[nx];
vector<pair<ll, ll>> dp[nx];
priority_queue<pair<ll, ll>> pq;

void dfs(int u, ll sm, ll mn, int rt)
{
    vs[u]=1;
    sm+=c[u];
    if (sm>0)
    {
        dp[rt].push_back({sm, mn});
        if (!d[u].empty()) dfs(d[u][0], 0, 0, rt);
    }
    else if (!d[u].empty()) dfs(d[u][0], sm, min(mn, sm), rt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    cur=s;
    for (int i=1; i<=n; i++) 
    {
        cin>>c[i]>>p;
        if (p!=0) d[p].push_back(i);
    }
    for (int i=1; i<=n; i++) if (!vs[i]) dfs(i, 0, 0, i);
    for (int i=1; i<=n; i++) reverse(dp[i].begin(), dp[i].end());
    for (int i=1; i<=n; i++) if (!dp[i].empty()) pq.push({dp[i].back().second, i});
    while (!pq.empty())
    {
        auto [_, idx]=pq.top();
        pq.pop();
        if (-dp[idx].back().second>cur) break;
        cur+=dp[idx].back().first;
        dp[idx].pop_back();
        if (!dp[idx].empty()) pq.push({dp[idx].back().second, idx});
    }
    cout<<cur-s;
}

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