Submission #1276719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276719		HiepVu217	Jobs (BOI24_jobs)	C++20	0 / 100	96 ms	18668 KiB

Main

//Proud of You//
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 3e5 + 17;
int n, a[N], c[N];
bool ex[N];
long long s;
vector <int> adj[N];
priority_queue <pair <int, int>> pq;
inline void dfs (int u, long long sm)
{
    ex[u] = (sm > 0);
    for (int v: adj[u])
    {
        dfs (v, sm + a[v]);
        ex[u] |= ex[v];
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    for (int i = 1, j; i <= n; ++i)
    {
        cin >> a[i] >> j;
        if (j)
        {
            adj[j].push_back(i);
            ++c[i];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            dfs (i, a[i]);
            if (ex[i])
            {
                pq.push ({a[i], i});
            }
        }
    }
    long long ans = s, z = 0;
    while (!pq.empty())
    {
        auto [au, u] = pq.top();
        pq.pop();
        if (s + z + au < 0)
        {
            continue;
        }
        z += au, ans = max (ans, z);
        for (int v: adj[u])
        {
            --c[v];
            if (!c[v] && ex[v])
            {
                pq.push ({a[v], v});
            }
        }
    }
    cout << ans;
}

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