Submission #1189967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189967		anmattroi	Jobs (BOI24_jobs)	C++17	14 / 100	2095 ms	31976 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;
int64_t c[maxn],s[maxn], T, mint[maxn];
ii edges[maxn];

int par[maxn], cl[maxn], dad[maxn], p[maxn];

vector<int> adj[maxn];

int find_set(int v) {
    return par[v] == v ? v : par[v] = find_set(par[v]);
}

void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    par[u] = v;
    c[v] += c[u];
}

void efs(int u) {
    for (int v : adj[u]) {
        dad[v] = u;
        efs(v);
    }
}

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] >> p[i];
        edges[i] = ii{p[i], i};
    }

    iota(par, par+n+1, 0);

    for (int i = 1; i <= n; i++) {
        auto [u, v] = edges[i];
        if (c[u] >= 0 && c[v] >= 0) union_set(u, v);
        else if (c[u] < 0 && c[v] < 0) union_set(u, v);
        else continue;

    }


    for (int i = 1; i <= n; i++) {
        auto [u, v] = edges[i];
        if ((c[u] >= 0 && c[v] >= 0) || (c[u] < 0 && c[v] < 0)) continue;

        adj[find_set(u)].emplace_back(find_set(v));
    }
    root = find_set(0);
    dad[root] = -1;
    efs(root);

    vector<int> debugHelper;

    for (int i = 0; i <= n; i++) debugHelper.emplace_back(find_set(i));
    sort(debugHelper.begin(), debugHelper.end());
    debugHelper.erase(unique(debugHelper.begin(), debugHelper.end()), debugHelper.end());

    for (int _ = 0; _ <= n; _++) {
        s[root] = 0; mint[root] = LLONG_MAX;
        pfs(root);
        int p = -1;
        int64_t mx = LLONG_MIN;
        for (int i : debugHelper) {
            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 = dad[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