Submission #1264779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264779		TsotneSV	Jobs (BOI24_jobs)	C++20	29 / 100	183 ms	48500 KiB

Main

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=3e5+5; 
const ll inf=1e9,INF=1e18; 

struct Tree {
    typedef ll T;
    static constexpr T unit = -INF;
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

int n,x[MAXN],p[MAXN]; ll s;
vi g[MAXN]; ll ans = 0; vi nodes;
array<ll,3> R[MAXN];

void dfs(int v) {
    for(int i : g[v]) dfs(i);
    nodes.pb(v);
}

void solve(int tc = 0){
    cin>>n>>s;

    rep(i,1,n+1) {
        cin>>x[i]>>p[i];
        g[p[i]].pb(i);
    }

    set<array<ll,3>> S;

    rep(i,1,n+1) {
        if(!p[i]) {
            dfs(i); ll sum = 0; int N = sz(nodes);
            Tree tr(N + 5); tr.update(0,0); 
            stack<pair<ll,int>> st; st.push({0,-1});

            rep(j,0,N) {
                sum += x[nodes[j]]; 
                while(st.size() and sum - st.top().fi <= 0) st.pop();
                if(st.empty()) R[nodes[j]] = {INF,0,0};
                else {
                    int l = st.top().se; ll k = sum - tr.query(l+1,j+2);
                    R[nodes[j]] = {-k,l == -1 ? 0 : nodes[l],sum - st.top().fi};
                } 
                
                st.push({sum,j});
                tr.update(j+1,sum);
            } S.ins(R[i]);

            nodes.clear();
        }
    }

    while(S.size()) {
        auto [drop,nxt,add] = *(S.begin()); S.erase(S.begin());
        if(s - drop < 0) break;
        s += add; ans += add; 
        if(nxt != 0) S.ins(R[nxt]);
    } print(ans);

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

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