Submission #1053107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053107		vjudge1	Portal (BOI24_portal)	C++17	0 / 100	2 ms	17240 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<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;
                }
            }

            if (sm < 0) continue;
            if (s + mn >= 0){
                s += sm;
                if (v != -1)
                    st.insert({-1, v});
                continue;
            }
            st.insert({-mn, u});
        }
        else{
            if (val > s)
                break;

            ll sm = 0;
            while (1){
                sm += a[v];

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

                if (sm >= 0){
                    break;
                }
            }

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

    cout << s << endl;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35