Submission #1027488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027488		sysia	Jobs (BOI24_jobs)	C++17	0 / 100	2087 ms	31392 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];
    }  
    vector<int>vis(n+1);
    int cc = 0;
    vector<bool>oncycle(n+1);
    auto detect_cycle = [&](int from){
        int v = from;
        while (1){
            oncycle[v] = 1;
            v = to[v];
            if (v == from) break;
        }
    };
    for (int i = 1; i<=n; i++){
        if (!vis[i]){
            cc++;
            int v = i;
            vis[v] = cc;
            while (!vis[v]){
                v = to[v];
                if (vis[v] == cc) {
                    detect_cycle(v);
                    break;
                } else break; //kawalek drzewa
            } 
        }
    }
    for (int i = 1; i<=n; i++){
        if (!oncycle[i]){
            g[to[i]].emplace_back(i);
            debug(to[i], i);
        }
    }
    vector<int>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;
    function<void(int, int)>sub = [&](int v, int ile){
        dp[v] -= ile;
        for (auto x: g[v]) sub(x, ile);
    };
    int ans = 0;
    while (1){
        T mx = {-oo, -oo};
        vector<int>ok(n+1);
        ok[0] = 1;
        function<void(int)>check = [&](int v){
            if (dp[v] < -s) return;
            ok[v] = 1;
            for (auto x: g[v]){
                check(x);
            } 
        };
        check(0);
        debug(ok);
        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;
        while (!vis[v]){
            vis[v] = 1;
            for (auto x: g[v]){
                if (!vis[x]){
                    sub(x, dp[v]);
                }
            }
            dp[v] = -oo;
            v = to[v];
        }
    }
    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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31