Submission #1028029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028029		mdn2002	Jobs (BOI24_jobs)	C++14	29 / 100	251 ms	34132 KiB

Main

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

void solve() {
    long long n, s, ans = 0;
    cin >> n >> s;
    vector<long long> x(n + 1);
    vector<int> p(n + 1), st, did(n + 1);
    vector<vector<int>> gr(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> x[i] >> p[i];
        if (p[i] == 0) st.push_back(i);
        else gr[p[i]].push_back(i);
    }

    set<pair<pair<long long, long long>, pair<int, int>>> ss;
    long long sum = 0, mn = 0;
    function<void(int, int)> go = [&] (int v, int a) {
        sum += x[v];
        mn = min(mn, sum);
        if (sum > 0) ss.insert({{-mn, sum}, {v, a}});
        else {
            for (auto u : gr[v]) go(u, a);
        }
    };
    function<void(int, int)> rgo = [&] (int v, int a) {
        did[v] = 1;
        for (auto u : gr[v]) {
            if (did[u]) continue;
            sum = mn = 0;
            go(u, u);
        }
        if (a != v) rgo(p[v], a);
    };
    for (auto v : st) {
        sum = mn = 0;
        go(v, v);
    }

    while (!ss.empty()) {
        auto [x, vv] = *ss.begin();
        ss.erase(ss.begin());
        long long mnn = x.first, summ = x.second;
        int v = vv.first, a = vv.second;
        if (mnn <= s && did[a] == 0) {
            s += summ, ans += summ;
            mn = sum = 0;
            did[a] = 1;
            rgo(v, a);
        }
    }
    cout << ans << endl;
}
/*
6 1
-1 0
2 1
3 2
-10 0
1 4
-2 5
*/
int main()
{
    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         auto [x, vv] = *ss.begin();
      |              ^

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