Submission #1049369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049369		aymanrs	Jobs (BOI24_jobs)	C++17	40 / 100	85 ms	25972 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct node {
    int p;
    long long x;
    vector<node*> l;
};
void dfs(node* n){
    for(node* c : n->l){
        dfs(c);
        if(c->x > 0) n->x += c->x;
    }
}
void solve(){
    int n;cin >> n;
    long long s;cin >> s;
    if(s == 1e18){
        node g[n+1];
        for(int i = 1;i <= n;i++){
            cin >> g[i].x >> g[i].p;
            g[g[i].p].l.push_back(&g[i]);
        }
        g[0].x=0;
        dfs(&g[0]);
        cout << g[0].x << '\n';
        return;
    }
    vector<int> v[n+1];
    int r[n+1];
    for(int i = 1;i <= n;i++){
        r[i]=i;int p,x;
        cin >> x >> p;
        if(p) {
            r[i]=r[p];
        }
        v[r[i]].push_back(x);
    }
    fill(r,r+n+1, 0);
    set<pair<int, int>> se;
    long long t[n+1] = {0};
    for(int i = 1;i <= n;i++){
        long long mi = 0;
        while(t[i] <= 0 && r[i] < v[i].size()){
            t[i] += v[i][r[i]];
            mi = min(mi,t[i]);
            r[i]++;
        }
        if(t[i]>0) se.insert({-mi, i});
    }
    long long os = s;
    while(!se.empty() && se.begin()->first<=s){
        int i = se.begin()->second;
        se.erase(se.begin());
        s += t[i];
        t[i]=0;
        long long mi = 0;
        while(t[i] <= 0 && r[i] < v[i].size()){
            t[i] += v[i][r[i]];
            mi = min(mi,t[i]);
            r[i]++;
        }
        if(t[i]>0) se.insert({-mi, i});
    }
    cout << s-os << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while(t[i] <= 0 && r[i] < v[i].size()){
      |                            ~~~~~^~~~~~~~~~~~~
Main.cpp:57:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(t[i] <= 0 && r[i] < v[i].size()){
      |                            ~~~~~^~~~~~~~~~~~~

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