제출 #1214317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214317		stefanneagu	Jobs (BOI24_jobs)	C++20	0 / 100	1020 ms	116144 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5 + 1;

multiset<pair<int, int>> con[nmax];
vector<int> adj[nmax];
int v[nmax];

void dfs(int i) {
    for (auto it : adj[i]) {
        dfs(it);
        cout << it << '\n';
        for (auto l : con[it]) {
            cout << l.first << " " << l.second << '\n';
        }
        cout << '\n';
        if (con[it].size() > con[i].size()) {
            swap(con[i], con[it]);
        }
        for (auto it : con[it]) {
            con[i].insert(it);
        }
        con[it].clear();
    }
    pair<int, int> tp = {max(0ll, -v[i]), v[i]};
    vector<pair<int, int>> des;
    for (auto it : con[i]) {
        if (tp.second <= 0) {
            tp = {max(tp.first, it.first - tp.second), tp.second + it.second};
            des.push_back(it);
        } else if (tp.first > it.first) {
            tp.second += it.second;
            des.push_back(it);
        } else {
            break;
        }
    }
    for (auto it : des) {
        con[i].erase(con[i].lower_bound(it));
    }
    if (tp.second <= 0) {
        return;
    }
    con[i].insert(tp);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        int tata;
        cin >> v[i] >> tata;
        adj[tata].push_back(i);
    }
    dfs(0);
    int xtra = 0;
    cout << "0\n";
    for (auto it : con[0]) {
        if (s + xtra >= it.first) {
            xtra += it.second;
        }
        cout << it.first << " " << it.second << '\n';
    }
    cout << xtra;
    return 0;
}

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