Submission #1023475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023475		serifefedartar	Jobs (BOI24_jobs)	C++17	100 / 100	301 ms	110144 KiB

Main

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 61
const ll MOD = 1e9 + 7;
const ll MAXN = 3e5 + 100;

#define int long long
vector<vector<int>> graph;
multiset<pair<int,int>> st[MAXN];
ll val[MAXN];

void dfs(int node) {
    for (auto u : graph[node]) {
        dfs(u);
        if (st[node].size() < st[u].size())
            swap(st[node], st[u]);

        for (auto v : st[u])
            st[node].insert(v);
    }

    if (val[node] >= 0)
        st[node].insert({0, val[node]});
    else if (graph[node].size()) {
        int req = val[node], now = val[node];

        // sete ekleyebilmek için now >= 0 olmalı
        while (st[node].size() && (now < 0 || st[node].begin()->f <= -req)) {
            pair<int,int> Q = *st[node].begin();
            st[node].erase(st[node].begin());

            req = min(req, now - Q.f);
            now += Q.s;
        }

        if (now >= 0)
            st[node].insert({-req, now});
    }
}

signed main() {
    fast
    ll N, s, p;
    cin >> N >> s;

    graph = vector<vector<int>>(N+1, vector<int>());
    for (int i = 1; i <= N; i++) {
        cin >> val[i] >> p;
        graph[p].push_back(i);
    }
    dfs(0);

    ll old = s;
    for (auto u : st[0]) {
        if (s >= u.f)
            s += u.s;
    }
    cout << s - old << "\n";
}

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