Submission #1238876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238876		Joshua_Andersson	Jobs (BOI24_jobs)	C++20	0 / 100	2095 ms	54388 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int inf = 1e18;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < (high); i++)
#define repp(i, lo, high) for (int i = (lo); i < (high); i++)
#define repe(i, container) for (auto& i : container)
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)

map<int, int> dp(int u, vvi & adj, vi & value)
{
    vector<map<int, int>> children;
    repe(e, adj[u])
    {
        map<int, int> c = dp(e, adj, value);
        children.push_back(c);
    }

    map<int, int> ret;
    int v = value[u];

    priority_queue<p2> pq;
    rep(i, sz(children))
    {
        if (sz(children[i])) pq.emplace(-begin(children[i])->first, i);
    }

    if (v>=0)
    {
        int s = 0;
        int p = v;
        int oldp = 0;
        while (sz(pq))
        {
            int x = -1;
            while (sz(pq))
            {
                auto [f, i] = pq.top();
                f = -f;
                if (s + p < f)
                {
                    x = f;
                    break;
                }
                pq.pop();
                p += begin(children[i])->second;
                children[i].erase(begin(children[i]));
                if (sz(children[i])) pq.emplace(-begin(children[i])->first, i);
            }
            ret[s] = p - oldp;
            if (x != -1)
            {
                s += x - p - s;
            }
            p = oldp;
        }
        ret[s] = max(ret[s], p - oldp);
    }
    else
    {
        int s = -v;
        int p = v;
        int oldp = 0;
        while (sz(pq))
        {
            int x = -1;
            while (sz(pq))
            {
                auto [f, i] = pq.top();
                f = -f;
                if (s + p < f)
                {
                    x = f;
                    break;
                }
                pq.pop();
                p += begin(children[i])->second;
                children[i].erase(begin(children[i]));
                if (sz(children[i])) pq.emplace(-begin(children[i])->first, i);
            }
            ret[s] = p - oldp;
            if (x != -1)
            {
                s += x - p - s;
            }
            p = oldp;
        }
        ret[s] = max(ret[s], p - oldp);
    }
    

    return ret;
}


signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n, s;
    cin >> n >> s;

    vi nodevalue(n+1);
    vvi adj(n+1);
    rep(i, n)
    {
        int p, v;
        cin >> v >> p;
        nodevalue[i] = v;
        if (p == 0) adj.back().push_back(i);
        else adj[p-1].push_back(i);
    }
    nodevalue.back() = s;
    map<int, int> res = dp(n, adj, nodevalue);
    cout << begin(res)->second-s;


    return 0;
}

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