Submission #1027550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027550		sysia	Jobs (BOI24_jobs)	C++17	14 / 100	2064 ms	28756 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void __print(int x){cerr << x;}
void __print(long long x){cerr << x;}
void __print(string x){cerr << "\"" << x << "\"";}
void __print(char x){cerr << "\'" << x << "\'";}
template<typename T, typename V>
void __print(pair<T, V>x){
    cerr << "{"; __print(x.first); cerr << ", "; __print(x.second); cerr << "}";
}
template<typename T>
void __print(T t){
    cerr << "{"; int f =0;
    for (auto i: t) {
        cerr << (f++ ? ", " : "");
        __print(i);
    }
    cerr << "}";
}
void _print(){cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v){
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = [", _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7;

void solve(){
    int n, s; cin >> n >> s;
    vector<int>a(n+1), to(n+1);
    vector<vector<int>>g(n+1);
    for (int i = 1; i<=n; i++){
        cin >> a[i] >> to[i];
        g[to[i]].emplace_back(i);
        debug(to[i], i);
    }  
    vector<int>vis(n+1), dp(n+1);
    function<void(int)>dfessa =[&](int v){
        for (auto x: g[v]){
            dp[x] = dp[v] + a[x];
            dfessa(x);
        }
    };
    dfessa(0);
    debug(dp);
    vis.assign(n+1, 0);
    vis[0] = 1;
    set<T>free;
    function<void(int, int)>sub = [&](int v, int ile){
        if (free.find({dp[v], v}) != free.end()){
            free.erase({dp[v], v});
            dp[v] -= ile;
            free.insert({dp[v], v});
        } else dp[v] -= ile;
        for (auto x: g[v]) sub(x, ile);
    };
    int ans = 0;
    vector<int>ok(n+1);
    ok[0] = 1;
    
    for (auto x: g[0]){
        free.insert({dp[x], x});
    }
    debug(free);
    while (1){
        T mx = {-oo, -oo};
        while ((int)free.size() && (*free.rbegin()).first >= -s) {
            int v = (*free.rbegin()).second;
            debug(2137, v);
            ok[v] = 1;
            free.erase(--free.end());
            for (auto x: g[v]){
                free.insert({dp[x], x});
            }
        }
        debug(free);
        for (int i = 1; i<=n; i++){
            if (ok[i]) {
                mx = max(mx, T{dp[i], i});
            }
        }
        if (mx.first <= 0) break;
        ans += mx.first;
        s += mx.first;
        debug(mx);
        int v = mx.second;
        int prev = -1;
        while (!vis[v]){
            vis[v] = 1;
            debug(v);
            for (auto x: g[v]){
                if (x != prev){
                    sub(x, dp[v]);
                }
            }
            free.erase({dp[v], v});
            dp[v] = -oo;
            prev = v;
            v = to[v];
        }
        debug(dp, free);
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

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