Submission #1214287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214287		stefanneagu	Jobs (BOI24_jobs)	C++20	0 / 100	214 ms	41476 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5 + 1;

multiset<pair<int, int>> con[nmax];
vector<int> adj[nmax];
int v[nmax];

void dfs(int i) {
    for (auto it : adj[i]) {
        dfs(it);
        if (con[it].size() > con[i].size()) {
            swap(con[i], con[it]);
        }
        for (auto it : con[it]) {
            con[i].insert(it);
        }
        con[it].clear();
    }
    pair<int, int> tp = {min(0ll, v[i]), v[i]};
    vector<pair<int, int>> des;
    for (auto it : con[i]) {
        if (tp.second > 0) {
            break;
        }
        tp = {max(tp.first, it.first - tp.second), tp.second + it.second};
        des.push_back(it);
    }
    for (auto it : des) {
        con[i].erase(con[i].lower_bound(it));
    }
    if (tp.second <= 0) {
        return;
    }
    if (con[i].size() == 0) {
        con[i].insert(tp);
        return;
    }
    des.clear();
    for (auto it : con[i]) {
        if (it.first <= tp.first) {
            tp.second += it.second;
            des.push_back(it);
        } else {
            break;
        }
    }
    for (auto it : des) {
        con[i].erase(con[i].lower_bound(it));
    }
    con[i].insert(tp);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, s;
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int tata;
        cin >> v[i] >> tata;
        adj[tata].push_back(i);
    }
    dfs(0);
    int xtra = 0;
    for (auto it : con[0]) {
        if (s + xtra >= it.first) {
            xtra += it.second;
        }
    }
    cout << xtra;
    return 0;
}

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