제출 #1274239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274239		vulestamenkovic	Jobs (BOI24_jobs)	C++20	29 / 100	136 ms	40492 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define MAXN (int)3e5+5
#define pq priority_queue
using namespace std;
#define ti tuple<int,int,int>
vector<int>g[MAXN];
pq<ti>p[MAXN];
int a[MAXN],m[MAXN];
//malo do veliko mesanje?!?!?!?!??!?!?!?!?!
pq<ti> merge(pq<ti>p1, pq<ti>p2){
    if(p1.size()>p2.size()){
        swap(p1,p2);
    }while(!p1.empty()){
        p2.push(p1.top());
        p1.pop();
    }
    return p2;
}
int ps(int u){
    while(!p[u].empty()){
        int d,b,c;
        tie(d,b,c)=p[u].top();p[u].pop();
        if(-d>m[u]){
            break;
        }
        if(g[b].size()>1){
            m[b]=m[u]+c;
            int x=ps(b);
            if(m[b]>=m[u]){
                m[u]=m[b];
                p[u]=merge(p[u],p[b]);
                continue;
            }
            p[u].emplace(x,u,c);
            continue;
        }
        if(c>-1){
            m[u]+=c;
            d=0,c=0;
        }
        for(int&x:g[b]){
            p[u].emplace(min(d,c+a[x]),x,c+a[x]);
        }
    }
    if(!p[u].empty()){
        int d,b,c;
        tie(d,b,c)=p[u].top();
        return d;
    }
    return -1e18;
}
void solve() {
    int n,s;cin>>n>>s;
    for(int i=1;i<=n;i++){
        int u;cin>>a[i]>>u;
        g[u].push_back(i);
        m[i]=-1;
    }for(int i=0;i<=n;i++){
        for(int&x:g[i]){
            p[i].emplace(min(0ll,a[x]),x,a[x]);
        }
    }

    m[0]=s;
    ps(0);
    cout<<m[0]-s<<'\n';
}
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int32_t T=1;//cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

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