Submission #1028887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028887		isaachew	Jobs (BOI24_jobs)	C++17	100 / 100	274 ms	39520 KiB

Main

#include <bits/stdc++.h>
/*
 Chains of jobs -> greedy
 Ignoring cycles, the graph is a forest
 If a path has a net profit and is attainable, take it
 When a job is taken, some jobs might have profits increased
 Segtree
 */
std::vector<std::vector<int>> children;
std::vector<int> parents,profits;
std::vector<long long> minspend;//min spend to make any profit
void insert(std::set<std::pair<long long,long long>>& mp,std::pair<long long,long long> nval){
    auto it=mp.lower_bound(nval);
    while(1){
        
        if(it!=mp.begin()){
            auto mit=it;
            --mit;
            if(mit->second>=nval.first){//merge left
                nval.second=mit->second-nval.first+nval.second;
                nval.first=mit->first;
                mp.erase(mit);
                continue;
            }
        }
        if(it!=mp.end()){
            if(it->first<=nval.second){//merge right
                nval.second=nval.second-it->first+it->second;
                it=mp.erase(it);
                continue;
            }
        }
        break;
    }
    mp.insert(nval);
}
void extend(std::set<std::pair<long long,long long>>& mp,long long val){
    if(val<0){
        while(!mp.empty()){
            std::pair<long long,long long> fv=*mp.begin();
            if(fv.second-fv.first+val>0){
                mp.erase(mp.begin());
                fv.first-=val;
                insert(mp,fv);
                return;
            }else{
                val=fv.second-fv.first+val;
                mp.erase(mp.begin());
            }
        }
    }else{
        insert(mp,{0,val});
    }
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;
    long long os,s;
    std::cin>>n>>os;
    s=os;
    parents.push_back(0);//root node
    profits.push_back(0);
    children.resize(n+1);
    for(int i=1;i<=n;i++){
        int a,b;
        std::cin>>a>>b;
        parents.push_back(b);
        profits.push_back(a);
        children[b].push_back(i);
    }
    std::vector<std::set<std::pair<long long,long long>>*> vec(n+1);
    for(int i=n;i>=0;i--){
        if(children[i].size()==0){
            vec[i]=new std::set<std::pair<long long,long long>>;
        }else{
            vec[i]=vec[children[i][0]];
            for(int j=1;j<children[i].size();j++){
                std::set<std::pair<long long,long long>>* st=vec[children[i][j]];
                if(st->size()>vec[i]->size())std::swap(st,vec[i]);
                for(std::pair<long long,long long> x:*st){
                    insert(*vec[i],x);
                }
                delete st;
            }
        }
        extend(*vec[i],profits[i]);
    }
    for(std::pair<long long,long long> x:*vec[0]){
        if(s>=x.first)s+=x.second-x.first;
    }
    delete vec[0];
    std::cout<<s-os<<'\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j=1;j<children[i].size();j++){
      |                         ~^~~~~~~~~~~~~~~~~~~

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