oj.uz

Submission #1011711

# Submission time Handle Problem Language Result Execution time Memory
1011711 2024-07-01T07:14:46 Z ttamx Jobs (BOI24_jobs) C++17
11 / 100
 358 ms 101560 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=3e5+5;

int n;
ll s;
ll a[N];
vector<int> adj[N];

struct DP{
    map<ll,ll> mp;
    void insert(ll x,ll d){
        mp[x]+=d;
        auto it=mp.find(x);
        if(it!=mp.begin()){
            auto x=prev(it),y=it;
            if(x->first+x->second>=y->first){
                it--;
                x->second+=y->second;
                mp.erase(y);
            }
        }
        for(auto x=it,y=next(it);y!=mp.end()&&x->first+x->second>=y->first;y=mp.erase(y)){
            x->second+=y->second;
        }
    }
    int size(){
        return mp.size();
    }
    void pop(ll x){
        ll sum=-x;
        for(auto it=mp.begin();it!=mp.end()&&(it->first<x||sum<0);it=mp.erase(it)){
            sum+=it->second;
        }
        insert(0,0);
        if(sum>0)insert(x,sum);
    }
}dp[N];

void dfs(int u){
    for(auto v:adj[u]){
        dfs(v);
        if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]);
        for(auto [x,y]:dp[v].mp)dp[u].insert(x,y);
    }
    if(a[u]>=0)dp[u].insert(0,a[u]);
    else dp[u].pop(-a[u]);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> s;
    for(int i=1;i<=n;i++){
        int p;
        cin >> a[i] >> p;
        adj[p].emplace_back(i);
    }
    dfs(0);
    ll ans=0;
    for(auto [x,y]:dp[0].mp)if(x<=s)ans+=y;
    cout << ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 88668 KB Output is correct
2 Correct 248 ms 68948 KB Output is correct
3 Correct 208 ms 50584 KB Output is correct
4 Correct 185 ms 60792 KB Output is correct
5 Correct 99 ms 67156 KB Output is correct
6 Correct 156 ms 54552 KB Output is correct
7 Correct 244 ms 75088 KB Output is correct
8 Correct 180 ms 51532 KB Output is correct
9 Correct 115 ms 64084 KB Output is correct
10 Correct 96 ms 66896 KB Output is correct
11 Correct 358 ms 101560 KB Output is correct
12 Correct 263 ms 85584 KB Output is correct
13 Correct 306 ms 93352 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 11 ms 21596 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Incorrect 8 ms 21596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 11 ms 21596 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Incorrect 8 ms 21596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 11 ms 21596 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Incorrect 8 ms 21596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 88668 KB Output is correct
2 Correct 248 ms 68948 KB Output is correct
3 Correct 208 ms 50584 KB Output is correct
4 Correct 185 ms 60792 KB Output is correct
5 Correct 99 ms 67156 KB Output is correct
6 Correct 156 ms 54552 KB Output is correct
7 Correct 244 ms 75088 KB Output is correct
8 Correct 180 ms 51532 KB Output is correct
9 Correct 115 ms 64084 KB Output is correct
10 Correct 96 ms 66896 KB Output is correct
11 Correct 358 ms 101560 KB Output is correct
12 Correct 263 ms 85584 KB Output is correct
13 Correct 306 ms 93352 KB Output is correct
14 Correct 8 ms 21596 KB Output is correct
15 Correct 11 ms 21596 KB Output is correct
16 Correct 8 ms 21596 KB Output is correct
17 Incorrect 8 ms 21596 KB Output isn't correct
18 Halted 0 ms 0 KB -