Submission #1081244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081244		raphaelp	Jobs (BOI24_jobs)	C++14	100 / 100	310 ms	68436 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct contrainte
{
    long long minimum, valeur;
};
bool operator<(contrainte a, contrainte b) { return a.minimum > b.minimum; }
void dfs(long long x, long long p, vector<vector<long long>> &AR, vector<contrainte> &X, vector<long long> &occ, priority_queue<contrainte> &PQ)
{
    occ[x] = 1;
    priority_queue<contrainte> PQ2;
    for (long long i = 0; i < AR[x].size(); i++)
    {
        dfs(AR[x][i], x, AR, X, occ, PQ2);
        if (PQ2.size() > PQ.size())
            swap(PQ2, PQ);
        while (!PQ2.empty())
        {
            PQ.push(PQ2.top());
            PQ2.pop();
        }
    }
    contrainte ans = X[x];
    while (!PQ.empty() && (ans.valeur < 0 || ans.minimum >= PQ.top().minimum - ans.valeur))
    {
        ans.minimum = max(ans.minimum, PQ.top().minimum - ans.valeur);
        ans.valeur += PQ.top().valeur;
        PQ.pop();
    }
    if (ans.valeur >= 0)
        PQ.push({ans.minimum, ans.valeur});
}
int main()
{
    long long N, S;
    cin >> N >> S;
    long long S2 = S;
    vector<long long> p(N);
    vector<contrainte> X(N);
    vector<vector<long long>> AR(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> X[i].valeur >> p[i];
        X[i].minimum = max((long long)0, -X[i].valeur);
        p[i]--;
        if (p[i] != -1)
            AR[p[i]].push_back(i);
    }
    vector<long long> occ(N);
    priority_queue<contrainte> PQ, PQ2;
    for (long long i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        dfs(i, i, AR, X, occ, PQ2);
        if (PQ2.size() > PQ.size())
            swap(PQ, PQ2);
        while (!PQ2.empty())
        {
            PQ.push(PQ2.top());
            PQ2.pop();
        }
    }
    while (!PQ.empty() && PQ.top().minimum <= S)
    {
        S += PQ.top().valeur;
        PQ.pop();
    }
    cout << S - S2;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, std::vector<std::vector<long long int> >&, std::vector<contrainte>&, std::vector<long long int>&, std::priority_queue<contrainte>&)':
Main.cpp:12:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (long long i = 0; i < AR[x].size(); i++)
      |                           ~~^~~~~~~~~~~~~~

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