Submission #1055685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055685		syxm1	Jobs (BOI24_jobs)	C++17	11 / 100	77 ms	32592 KiB

Main

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

#define int long long

/*
- the graph will be 'c' connected components with each cc is a tree
- we can process each cc individually
- greedy : only take a negative node if it's child can make sum that cover loss 
           from the current node.
*/

const int mxn = 3e5+20;
int n, s, x[mxn], dp[mxn];
vector<int> adj[mxn];

void dfs(int cur) {
    int sigma = 0;
    for (int nxt : adj[cur]) {
        dfs(nxt);
        sigma += dp[nxt];
    }
    dp[cur] = max(0ll, sigma + x[cur]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        int p;
        cin >> p;
        adj[p].push_back(i);
    }

    dfs(0);

    cout << dp[0] << '\n';
}   

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