Submission #1027976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027976		mdn2002	Jobs (BOI24_jobs)	C++14	29 / 100	189 ms	18116 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, gt(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> x[i] >> p[i];
        if (p[i] == 0) st.push_back(i);
        else gt[p[i]] = i;
    }

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

    while (!ss.empty()) {
        auto [x, v] = *ss.begin();
        ss.erase(ss.begin());
        long long mnn = x.first, summ = x.second;
        if (mnn <= s) {
            s += summ, ans += summ;
            mn = sum = 0;
            if (gt[v] != 0) go(gt[v]);
        }
        else break;
    }
    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:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto [x, v] = *ss.begin();
      |              ^

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