oj.uz

답안 #1011716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1011716 2024-07-01T07:24:14 Z ttamx Jobs (BOI24_jobs) C++17
11 / 100
 342 ms 105560 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;
        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){
        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)ans+=y;
    cout << ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 99664 KB Output is correct
2 Correct 302 ms 73552 KB Output is correct
3 Correct 226 ms 55628 KB Output is correct
4 Correct 123 ms 67668 KB Output is correct
5 Correct 119 ms 73040 KB Output is correct
6 Correct 166 ms 60752 KB Output is correct
7 Correct 303 ms 81472 KB Output is correct
8 Correct 225 ms 55828 KB Output is correct
9 Correct 117 ms 71640 KB Output is correct
10 Correct 109 ms 71248 KB Output is correct
11 Correct 342 ms 105560 KB Output is correct
12 Correct 283 ms 88904 KB Output is correct
13 Correct 327 ms 96596 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Incorrect 11 ms 23768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Incorrect 11 ms 23768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Incorrect 11 ms 23768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 99664 KB Output is correct
2 Correct 302 ms 73552 KB Output is correct
3 Correct 226 ms 55628 KB Output is correct
4 Correct 123 ms 67668 KB Output is correct
5 Correct 119 ms 73040 KB Output is correct
6 Correct 166 ms 60752 KB Output is correct
7 Correct 303 ms 81472 KB Output is correct
8 Correct 225 ms 55828 KB Output is correct
9 Correct 117 ms 71640 KB Output is correct
10 Correct 109 ms 71248 KB Output is correct
11 Correct 342 ms 105560 KB Output is correct
12 Correct 283 ms 88904 KB Output is correct
13 Correct 327 ms 96596 KB Output is correct
14 Correct 11 ms 23896 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Incorrect 11 ms 23768 KB Output isn't correct
17 Halted 0 ms 0 KB -