oj.uz

Submission #1011732

# Submission time Handle Problem Language Result Execution time Memory
1011732 2024-07-01T07:47:59 Z ttamx Jobs (BOI24_jobs) C++17
11 / 100
 203 ms 71584 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;
    }
    int size(){
        return mp.size();
    }
    void pop(ll x){
        auto it=mp.begin();
        ll cur=-x;
        ll last=x;
        for(;it!=mp.end()&&cur<0;it=mp.erase(it)){
            last=max(last,it->first-cur);
            cur+=it->second;
        }
        for(;it!=mp.end();it=mp.erase(it)){
            cur+=it->second;
        }
        if(cur>0)insert(last,cur);
        insert(0,0);
    }
}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)s+=y,ans+=y;
    cout << ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 40724 KB Output is correct
2 Correct 142 ms 47160 KB Output is correct
3 Correct 203 ms 53072 KB Output is correct
4 Correct 100 ms 63200 KB Output is correct
5 Correct 113 ms 71584 KB Output is correct
6 Correct 68 ms 33872 KB Output is correct
7 Correct 129 ms 46416 KB Output is correct
8 Correct 194 ms 53840 KB Output is correct
9 Correct 91 ms 68364 KB Output is correct
10 Correct 91 ms 71508 KB Output is correct
11 Correct 140 ms 44788 KB Output is correct
12 Correct 123 ms 40964 KB Output is correct
13 Correct 136 ms 44888 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 40724 KB Output is correct
2 Correct 142 ms 47160 KB Output is correct
3 Correct 203 ms 53072 KB Output is correct
4 Correct 100 ms 63200 KB Output is correct
5 Correct 113 ms 71584 KB Output is correct
6 Correct 68 ms 33872 KB Output is correct
7 Correct 129 ms 46416 KB Output is correct
8 Correct 194 ms 53840 KB Output is correct
9 Correct 91 ms 68364 KB Output is correct
10 Correct 91 ms 71508 KB Output is correct
11 Correct 140 ms 44788 KB Output is correct
12 Correct 123 ms 40964 KB Output is correct
13 Correct 136 ms 44888 KB Output is correct
14 Incorrect 3 ms 23128 KB Output isn't correct
15 Halted 0 ms 0 KB -