Submission #1028063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028063		mdn2002	Jobs (BOI24_jobs)	C++14	0 / 100	186 ms	22552 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), mnnn(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<vector<int>, int>>> ss;
    long long sum = 0, mn = 0, alsum = 0;
    vector<int> vv;
    function<void(int)> go = [&] (int v) {
        sum += x[v];
        mnnn[v] = mnnn[p[v]] + x[v];
        mn = min(mn, mnnn[v]);
        if (sum > 0) {
            vv.push_back(v);
            alsum += sum;
        }
        else {
            for (auto u : gr[v]) {
                go(u);
                sum = 0;
            }
        }
    };
    function<void(int, int)> rgo = [&] (int v, int a) {
        did[v] = 1;
        for (auto u : gr[v]) {
            if (did[u]) continue;
            alsum = sum = mn = mnnn[u] = 0;
            vv.clear();
            go(u);
            if (alsum > 0) ss.insert({{mn, alsum}, {vv, u}});
        }
        if (a != v && did[p[v]] == 0) rgo(p[v], a);
    };
    for (auto v : st) {
        alsum = sum = mn = mnnn[v] = 0;
        vv.clear();
        go(v);
        if (alsum > 0) ss.insert({{mn, alsum}, {vv, v}});
    }

    while (!ss.empty()) {
        auto [x, vv] = *ss.begin();
        ss.erase(ss.begin());
        long long mnn = x.first, summ = x.second;
        vector<int> vvv = vv.first;
        int a = vv.second;
        if (mnn <= s && did[a] == 0) {
            s += summ, ans += summ;
            for (auto v : vvv) 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:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         auto [x, vv] = *ss.begin();
      |              ^

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