Submission #1238853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238853		Joshua_Andersson	Jobs (BOI24_jobs)	C++20	14 / 100	2094 ms	38480 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)

void gather(int u, vvi& adj, vi& value, deque<int>& arr)
{
    arr.push_back(value[u]);
    repe(e, adj[u]) gather(e, adj, value, arr);
}

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;
    
    vector<deque<int>> children;
    repe(e, adj[n])
    {
        children.push_back({});
        gather(e, adj, nodevalue, children.back());
    }

    int ans = nodevalue.back();

    while (true)
    {
        bool any = false;

        repe(c, children)
        {
            int p = ans;
            int k = -1;
            rep(i, sz(c))
            {
                p += c[i];
                if (p < 0) break;
                if (p > ans)
                {
                    k = i+1;
                    break;
                }
            }
            if (k!=-1)
            {
                any = 1;
                ans = p;
                rep(i, k) c.pop_front();
            }
        }

        if (!any) break;
    }

    cout << ans-nodevalue.back();

    return 0;
}

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