Submission #1042209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042209		aaaaaarroz	Jobs (BOI24_jobs)	C++17	0 / 100	185 ms	32256 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n, s;
    cin >> n >> s;
    vector<vector<ll>> graph(n);
    vector<ll> ganancias(n);
    vector<int> dependencia(n, 0);
    for (ll i = 0; i < n; i++) {
        ll vecino;
        cin >> ganancias[i] >> vecino;
        if (vecino > 0) {
            graph[vecino - 1].push_back(i);
            dependencia[i]++;
        }
    }
    priority_queue<pair<ll, ll>> auxiliar;
    for (ll i = 0; i < n; i++) {
        if (dependencia[i] == 0) {
            ll sumar = 0, max_ganancia = 0;
            priority_queue<pair<ll, ll>> pq;
            pq.push({ganancias[i], i});
            while (!pq.empty()) {
                auto [current_sum, nodo] = pq.top();
                pq.pop();

                sumar += current_sum;
                max_ganancia = max(max_ganancia, sumar);
                auxiliar.push({sumar, max_ganancia});

                for (ll vecino : graph[nodo]) {
                    pq.push({ganancias[vecino], vecino});
                }
            }
        }
    }
    int s_inicial=s;
    while (!auxiliar.empty()) {
        auto [sumar, max_ganancia] = auxiliar.top();
        auxiliar.pop();
        if (s + sumar >= 0 && (s + max_ganancia) >= s) {
            s += max_ganancia;
        }
    }
    cout << s-s_inicial << "\n";
    return 0;
}

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