Submission #1244516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244516		Amaarsaa	Jobs (BOI24_jobs)	C++20	0 / 100	2097 ms	150644 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll =  long long;
using pll = pair < ll, ll >;
const ll N = 1e6 + 2;

vector < ll > adj[N];
ll depth[N], cost[N], sz[N], a[N], pos[N];
ll timer = 0, n;
ll anc[N], par[N];


vector < pair < ll, ll > > dep;

struct ST {
    ll mn, sum, has = 0;
};

ST F;
ST T[4 * N];

void Build(ll p, ll lo, ll hi) {
    if ( lo == hi){
        T[p].mn = a[lo];
        T[p].sum = a[lo];
        T[p].has = 0;
        return ;
    }
    ll mid = (lo + hi)/2;

    Build(2 * p, lo, mid);
    Build(2 * p + 1, mid + 1, hi);
    
    T[p].sum = T[2 * p].sum + T[2 * p + 1].sum;
    T[p].mn = min(T[2 * p + 1].mn ,T[2 * p + 1].mn);
    T[p].has = 0;
}

void PushDown(ll p, ll lo, ll hi) {
    if ( T[p].has == 0) return ;
    T[p].sum = T[p].mn = 0;
    if ( lo == hi) return ;
    T[2 * p].has = T[2 * p + 1].has = 1;
    
    return ;
}

void Find(ll p, ll lo, ll hi, ll l, ll r) {
    PushDown(p, lo, hi);
    
    if ( l > hi || lo > r) return ;
    if ( l <= lo && hi <= r) {
        F.mn = min(F.mn, T[p].mn);
        F.sum = F.sum + T[p].sum;
        return ;
    }
    ll mid = (lo + hi)/2;
    Find(2 * p, lo, mid, l, r);
    Find(2 * p + 1, mid + 1, hi, l, r);
    return ;
}

void Update(ll p, ll lo, ll hi, ll l, ll r) {
    PushDown(p, lo, hi);
    
    if ( l > hi || lo > r) return ;
    if ( l <= lo && hi <= r) {
        T[p].has = 1;
        return ;
    }
    ll mid = (lo + hi)/2;
    Update(2 * p, lo, mid, l, r);
    Update(2 * p + 1, mid + 1, hi, l, r);
    return ;
}

void query(ll x, ll y) {
    F.mn =1e18;
    F.sum = 0;
    while ( anc[x] != anc[y]) {
        if ( depth[anc[x]] < depth[anc[y]] ) swap(x, y);
        Find(1, 1, n + 1, pos[anc[x]], pos[x]);
        x =par[anc[x]];
    }

    if ( pos[x] > pos[y]) swap(x, y);
    Find(1, 1, n + 1, pos[x], pos[y]);
}
void update_query(ll x, ll y) {
    F.mn =1e18;
    F.sum = 0;
    for ( ; anc[x] != anc[y]; x = par[anc[x]]) {
        if ( depth[anc[x]] < depth[anc[y]] ) swap(x, y);
        Update(1, 1, n + 1, pos[anc[x]], pos[x]);
    }
    if ( pos[x] > pos[y]) swap(x, y);
    Update(1, 1, n + 1, pos[x], pos[y]);
}


ll Go(ll node, ll par) {
    sz[node] = 1;
    for ( ll nxt : adj[node]) {
        if ( nxt == par) continue;
        depth[nxt] = depth[node] + 1;
        sz[node] += Go(nxt, node);
    }
    return sz[node];
}

void HLD(ll node, ll par, ll king) {
    timer ++;
    a[timer] = cost[node];
    pos[node] = timer;
    anc[node] = king;
    ll heavy_node , heavy_sz;

    heavy_node = heavy_sz = -1;
    
    for ( ll nxt :adj[node]) {
        if ( nxt == par) continue;
        if ( heavy_sz < sz[nxt]) {
            heavy_sz = sz[nxt];
            heavy_node = nxt;
        }    
    }

    if ( heavy_node == -1) return;

    HLD(heavy_node, node, king);

    for ( ll nxt : adj[node]) {
        if ( nxt == par || nxt == heavy_node) continue;
        HLD(nxt, node, nxt);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll m, r, s, y, i, ind, x, t;


    cin >> n >> m;
    for (i = 1; i <= n; i ++) {
        cin >> cost[i] >> par[i];
        adj[par[i]].push_back(i);
    }
    Go(0, 0);
    HLD(0, 0, 0);

    Build(1, 1, n + 1);

    vector < pair < ll, ll > > v;

    for (i = 0; i <= n; i++) {
        v.push_back(make_pair(depth[i], i));
    }

    sort(v.begin(), v.end());
    priority_queue < pair < ll, pll >  > pq;

        F.mn = 1e18;
        F.sum = 0;
    // for (i = 1; i <= n; i ++) {
    //     cout << anc[i] << " ";
    // }
    // cout << endl;
    ll mn, sum, profit;
    profit = 0;
    for (ind = 0; ind < v.size(); ind ++) {
        x = v[ind].second;
        query(x, 0);
        if ( F.sum <= 0) continue;
        pq.push(make_pair(F.mn, make_pair(F.sum, x)));
        while ( !pq.empty()) {
            mn = pq.top().first;
            sum=  pq.top().second.first;
            ind = pq.top().second.second;
            if ( m + mn >= 0) {
                m += sum;
                profit +=sum;
                update_query(ind, 0);
                pq.pop();
            }
            else break;
        }
    }
    cout << profit << endl;
}

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