Submission #1165980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165980		Math4Life2020	Jobs (BOI24_jobs)	C++20	100 / 100	292 ms	110348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 3e5+5;
map<ll,ll> m0[Nm];

ll fz(ll a, ll b) {
    if (a==-1) {
        return b;
    }
    if (b==-1) {
        return a;
    }
    if (m0[a].size()>m0[b].size()) {
        swap(a,b);
    }
    for (pii p0: m0[a]) {
        m0[b][p0.first]+=p0.second;
    }
    //cout << "fusing, returning b="<<b<<"\n";
    return b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,S; cin >> N >> S;
    ll x[N]; ll p[N];
    vector<ll> fadj[N];
    vector<ll> fadjZ; //fadj zero
    ll madd[N]; //memory address
    for (ll i=0;i<N;i++) {
        cin >> x[i] >> p[i];
        madd[i]=i;
        p[i]--;
        if (p[i]==-1) {
            fadjZ.push_back(i);
        } else {
            fadj[p[i]].push_back(i);
        }
    }
    for (ll y=(N-1);y>=0;y--) {
        for (ll z: fadj[y]) {
            madd[y]=fz(madd[y],madd[z]);
        }
        ll A = madd[y];
        if (x[y]>=0) {
            m0[A][0]+=x[y];
        } else {
            vector<ll> delc; //delete coordinates
            ll val = -x[y]; //negative of value
            ll ov = -x[y]; //current overheard
            while (!m0[A].empty() && val>0) {
                auto A0 = m0[A].begin();
                pii pstr = *A0; //{operation overhead, additional value}
                m0[A].erase(A0);
                ov = max(ov,pstr.first+val);
                val = val - pstr.second;
            } 
            if (val<=0) {
                m0[A][ov]+=(-val);
            }
        }
    }
    ll A= -1;
    for (ll y: fadjZ) {
        A = fz(A,madd[y]);
    }
    ll S0 = S;
    while (!m0[A].empty()) {
        auto A0 = m0[A].begin();
        pii p0 = *A0;
        m0[A].erase(A0);
        if (S>=p0.first) {
            S += p0.second;
        } else {
            break;
        }
    }
    cout << (S-S0) << "\n";
}

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