oj.uz

Submission #991606

# Submission time Handle Problem Language Result Execution time Memory
991606 2024-06-02T15:43:55 Z VMaksimoski008 Jobs (BOI24_jobs) C++17
11 / 100
 71 ms 26380 KB 
#include <bits/stdc++.h>
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Node = array<ll, 3>;
 
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 3e5 + 5;
const double eps = 1e-9;
 
int n;
ll val[maxn], S, sub[maxn], req[maxn];
vector<int> graph[maxn];
 
ll dfs(int u) {
    ll sum = val[u];
    for(int &v : graph[u]) sum += dfs(v);
    return max(0ll, sum);
}

void dfs2(int u, int p) {
    sub[u] = val[u];
    req[u] = max(0ll, -val[u]);

    for(int &v : graph[u]) {
        dfs2(v, u);
        sub[u] += sub[v];
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
 
    cin >> n >> S;
    for(int i=1; i<=n; i++) {
        cin >> val[i];
        int p;
        cin >> p;
        graph[p].push_back(i);
    }

    if(S == 1e18) {
        cout << dfs(0) << '\n';
        return 0;
    }
 
    //line glhf
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    for(int &x : graph[0]) {
        dfs2(x, 0);
        pq.push({ req[x], sub[x] });
    }

    ll ans = S, curr = S;

    while(!pq.empty()) {
        auto [need, can, u] = pq.top(); pq.pop();
        ans = max(ans, curr);

        if(val[u] >= 0) curr += val[u];
        
        if(curr >= need) {
            if(val[u] < 0) curr += val[u];
            if(graph[u].size() > 0) {
                int nxt = graph[u][0];
                pq.push({ req[nxt], sub[nxt], nxt });
            }
        }

    }   

    cout << ans - S << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22864 KB Output is correct
2 Correct 61 ms 21396 KB Output is correct
3 Correct 67 ms 20876 KB Output is correct
4 Correct 62 ms 25220 KB Output is correct
5 Correct 58 ms 26380 KB Output is correct
6 Correct 56 ms 18004 KB Output is correct
7 Correct 65 ms 21344 KB Output is correct
8 Correct 60 ms 21328 KB Output is correct
9 Correct 56 ms 25072 KB Output is correct
10 Correct 53 ms 26188 KB Output is correct
11 Correct 67 ms 22368 KB Output is correct
12 Correct 54 ms 20304 KB Output is correct
13 Correct 66 ms 22868 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 2 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 2 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 2 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22864 KB Output is correct
2 Correct 61 ms 21396 KB Output is correct
3 Correct 67 ms 20876 KB Output is correct
4 Correct 62 ms 25220 KB Output is correct
5 Correct 58 ms 26380 KB Output is correct
6 Correct 56 ms 18004 KB Output is correct
7 Correct 65 ms 21344 KB Output is correct
8 Correct 60 ms 21328 KB Output is correct
9 Correct 56 ms 25072 KB Output is correct
10 Correct 53 ms 26188 KB Output is correct
11 Correct 67 ms 22368 KB Output is correct
12 Correct 54 ms 20304 KB Output is correct
13 Correct 66 ms 22868 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Incorrect 2 ms 12888 KB Output isn't correct
16 Halted 0 ms 0 KB -