Submission #1080316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080316		someone	Jobs (BOI24_jobs)	C++14	100 / 100	300 ms	40656 KiB

Main

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using namespace std;

const int N = 3e5 + 42;

struct Node {
    i64 i, sub, add, gain;

    bool operator <(const Node& other) const {
        if(max(sub, other.sub - gain) == max(other.sub, sub - other.gain)) {
            if(gain == other.gain)
                return i < other.i;
            return gain > other.gain;
        }
        return max(sub, other.sub - gain) < max(other.sub, sub - other.gain);
    }
};

int par[N];

int F(int i) {
    if(par[i] == i) return i;
    return par[i] = F(par[i]);
}

void U(int a, int b) {
    a = F(a), b = F(b);
    par[b] = a;
}

Node merge(Node a, Node b) {
    Node ans;
    ans.i = a.i;
    ans.sub = max(a.sub, b.sub - a.gain);
    ans.gain = a.gain + b.gain;
    ans.add = ans.gain + ans.sub;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    i64 s; cin >> s;
    set<Node> pq;
    vector<int> p(n+1);
    vector<Node> node(n+1);
    for(int i = 1; i <= n; i++) {
        node[i].i = i;
        par[i] = i;
        i64 x; cin >> x >> p[i];
        node[i].gain = x;
        if(x < 0) {
            node[i].sub = -x, node[i].add = 0;
        } else {
            node[i].add = x, node[i].sub = 0;
        }
        pq.insert(node[i]);
    }

    while(!pq.empty()) {
        auto it = pq.begin();
        Node x = *it;
        Node fus = merge(node[F(p[x.i])], x);
        if(!(F(p[x.i]) == 0 && (fus.sub > s || x.gain < 0))) {
            U(p[x.i], x.i);
            pq.erase(it);
            if(F(p[x.i]) != 0) {
                pq.erase(node[F(p[x.i])]);
                pq.insert(fus);
            }
            node[F(p[x.i])] = fus;
        } else {
            pq.erase(it);
        }
    }
    cout << max(0ll, node[0].gain) << '\n';
}

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