Submission #1276721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276721		HiepVu217	Jobs (BOI24_jobs)	C++20	0 / 100	100 ms	20796 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, f[N];
vector <int> adj[N];
priority_queue <pair <int, int>> pq;
inline void dfs (int u, long long sm)
{
    f[u] = a[u];
    for (int v: adj[u])
    {
        dfs (v, sm + a[u]);
        if (f[v] > 0)
        {
            f[u] += f[v];
        }
    }
    if (sm + f[u] > 0)
    {
        ex[u] = 1;
    }
}
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, 0);
            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