Submission #1030828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030828		boris_mihov	Jobs (BOI24_jobs)	C++17	0 / 100	1419 ms	1048576 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

typedef long long llong;
const int MAXN = 300000 + 10;
const int MOD = 1e9 + 7;
const llong INF = 1e18;
const int INTINF = 1e9;

int n;
struct Eat
{
    llong required;
    llong profit;

    friend Eat operator + (const Eat &a, const Eat &b)
    {
        if (a.required > b.required)
        {
            return b + a;
        }
        
        return {std::max(0LL, std::max(a.required, b.required - a.profit)), a.profit + b.profit};
    }
};

llong a[MAXN];
llong dp[MAXN];
std::vector <int> g[MAXN];
std::vector <Eat> eat[MAXN];

void dfs(int node, int par)
{
    eat[node].push_back({0, 0});
    for (const int &u : g[node])
    {
        if (u != par)
        {
            dfs(u, node);
            std::vector <Eat> result;
            for (const Eat &first : eat[node])
            {
                for (const Eat &second : eat[u])
                {
                    result.push_back(first + second);
                }
            }

            eat[node] = result;
        }
    }

    for (Eat &curr : eat[node])
    {
        curr.required = std::max(0LL, std::max(-a[node], curr.required - a[node]));
        curr.profit += a[node];
    }

    if (a[node] < 0) 
    {
        eat[node].push_back({0, 0});
    }

    // std::cout << "eat: " << node << '\n';
    // for (const auto &[required, profit] : eat[node])
    // {
    //     std::cout << required << ' ' << profit << '\n';
    // }
}

void solve()
{
    dfs(1, 0);
    llong max = 0;
    for (const Eat &current : eat[1])
    {
        if (current.required == 0)
        {
            max = std::max(max, current.profit);
        }
    }

    assert(max >= a[1]);
    std::cout << max - a[1] << '\n';
}

void input()
{
    std::cin >> n >> a[1]; n++;
    for (int i = 2 ; i <= n ; ++i)
    {
        int p;
        std::cin >> a[i] >> p;
        g[p + 1].push_back(i);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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