Submission #1189970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189970		anmattroi	Jobs (BOI24_jobs)	C++17	14 / 100	2096 ms	24840 KiB

Main

#include <bits/stdc++.h>
#define maxn 300005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, root;
int c[maxn];
int64_t s[maxn], T, mint[maxn];
ii edges[maxn];
int cl[maxn], par[maxn];

vector<int> adj[maxn];


void pfs(int u) {
    if (cl[u]) {
        s[u] = 0;
        mint[u] = LLONG_MAX;
    }
    else {
        mint[u] = min(mint[u], s[u] += c[u]);
    }
    for (int v : adj[u]) {
        s[v] = s[u];
        mint[v] = mint[u];
        pfs(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> T;
    int64_t old = T;
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> par[i];
        adj[par[i]].emplace_back(i);
    }

    par[0] = -1;


    for (int _ = 0; _ <= n; _++) {
        s[0] = 0; mint[0] = LLONG_MAX;
        pfs(0);
        int p = -1;
        int64_t mx = LLONG_MIN;
        for (int i = 0; i <= n; i++) {
            if (!cl[i] && s[i] >= 0 && -mint[i] <= T && mx < s[i]) {
                mx = s[i];
                p = i;
            }
        }

        if (p == -1) break;

        T += s[p];

        while (p != -1) {
            cl[p] = 1;
            p = par[p];
        }


    }
    cout << T - old;
}
/*
6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5

6
*/

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