oj.uz

Submission #1011722

# Submission time Handle Problem Language Result Execution time Memory
1011722 2024-07-01T07:32:08 Z ttamx Jobs (BOI24_jobs) C++17
11 / 100
 325 ms 106580 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;
    ll lz;
    DP():lz(0){}
    void insert(ll x,ll d){
        x-=lz;
        mp[x]+=d;
    }
    int size(){
        return mp.size();
    }
    void pop(ll x){
        lz+=x;
        auto it=mp.begin();
        ll cur=-x;
        for(;it!=mp.end();it=mp.erase(it)){
            it->second+=cur;
            if(it->second>0)break;
            cur=it->second;
        }
        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+dp[v].lz,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+dp[0].lz<=s)s+=y,ans+=y;
    cout << ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 98196 KB Output is correct
2 Correct 260 ms 75536 KB Output is correct
3 Correct 240 ms 58444 KB Output is correct
4 Correct 113 ms 65104 KB Output is correct
5 Correct 118 ms 75600 KB Output is correct
6 Correct 171 ms 59056 KB Output is correct
7 Correct 263 ms 83624 KB Output is correct
8 Correct 220 ms 58584 KB Output is correct
9 Correct 95 ms 72272 KB Output is correct
10 Correct 107 ms 76656 KB Output is correct
11 Correct 284 ms 106580 KB Output is correct
12 Correct 255 ms 89684 KB Output is correct
13 Correct 261 ms 95316 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 98196 KB Output is correct
2 Correct 260 ms 75536 KB Output is correct
3 Correct 240 ms 58444 KB Output is correct
4 Correct 113 ms 65104 KB Output is correct
5 Correct 118 ms 75600 KB Output is correct
6 Correct 171 ms 59056 KB Output is correct
7 Correct 263 ms 83624 KB Output is correct
8 Correct 220 ms 58584 KB Output is correct
9 Correct 95 ms 72272 KB Output is correct
10 Correct 107 ms 76656 KB Output is correct
11 Correct 284 ms 106580 KB Output is correct
12 Correct 255 ms 89684 KB Output is correct
13 Correct 261 ms 95316 KB Output is correct
14 Incorrect 10 ms 23896 KB Output isn't correct
15 Halted 0 ms 0 KB -