제출 #1053031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053031		vjudge1	Jobs (BOI24_jobs)	C++17	0 / 100	40 ms	24916 KiB

Main

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

typedef long long ll;

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

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

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

    while (!st.empty()){
        auto [val, v] = *st.begin();
        st.erase(st.begin());

        // cout << endl << "At " << v << " with val = " << val << endl;

        if (val == -1){
            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;
            }
            // cout << mn << " -- " << sm << endl;

            if (sm < 0){
                // cout << "sm < 0" << endl;
                continue;
            }
            st.insert({-mn, u});
        }
        else{
            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;
            }

            // cout << sm << ", now at " << v << endl;
            if (sm < 0 or (s + mn) < 0) continue;

            if (v != -1)
                st.insert({-1, v});

            s += sm;
        }
    }

    cout << s << endl;
}

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