Submission #1081239

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1081239	2024-08-29 20:05:00	raphaelp	Jobs (BOI24_jobs)	C++14	100 / 100	332 ms	91220 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
void dfs(long long x, long long p, vector<vector<long long>> &AR, vector<long long> &X, vector<long long> &req, vector<long long> &occ, priority_queue<pair<long long, long long>> &PQ)
{
    occ[x] = 1;
    priority_queue<pair<long long, long long>> PQ2;
    for (long long i = 0; i < AR[x].size(); i++)
    {
        dfs(AR[x][i], x, AR, X, req, occ, PQ2);
        if (PQ2.size() > PQ.size())
            swap(PQ2, PQ);
        while (!PQ2.empty())
        {
            PQ.push(PQ2.top());
            PQ2.pop();
        }
    }
    pair<long long, long long> ans = {req[x], X[x]};
    while (!PQ.empty() && (ans.second < 0 || ans.first >= -PQ.top().first - ans.second))
    {
        ans.first = max(ans.first, -PQ.top().first - ans.second);
        ans.second += PQ.top().second;
        PQ.pop();
    }
    if (ans.second >= 0)
        PQ.push({-ans.first, ans.second});
}
int main()
{
    long long N, S;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, std::vector<std::vector<long long int> >&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&, std::priority_queue<std::pair<long long int, long long int> >&)':
Main.cpp:7: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]
    7 |     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