Submission #1053083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053083		vjudge1	Jobs (BOI24_jobs)	C++17	0 / 100	125 ms	36692 KiB

Main

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

typedef long long ll;

const ll N = 3e5 + 10;
ll n, s, a[N], p[N];
vector<ll> outward[N], inward[N];

int main(){
    cin >> n >> s;
    set<ll> st;
    for (ll i = 1; i <= n; i ++){
        cin >> a[i] >> p[i];
        if (!p[i]){
            st.insert(i);
            continue;
        }

        outward[p[i]].push_back(i);
        inward[i].push_back(p[i]);
    }

    for (ll ii = 0; ii <= n * 10; ii ++){
        for (ll v : st){
            ll u = v;
            ll sm = 0;
            ll mn = 0;
            while (1){
                sm += a[v];
                mn = min(mn, sm);

                if (outward[v].size())
                    v = outward[v][0];
                else
                    v = -1;

                if (sm >= 0 or v == -1){
                    break;
                }
            }

            if (sm < 0){
                st.erase(u);
                break;
            }

            if (s + mn < 0) continue;

            st.erase(u);
            if (v != -1)
                st.insert(v);
            s += sm;

            break;
        }
    }

    cout << s << endl;
}

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