Submission #1254068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254068		BuiDucManh123	Jobs (BOI24_jobs)	C++20	0 / 100	245 ms	73012 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define ld long double
const int mod = 1e9+7;
using namespace std;
#define int ll
int x[300009], cost[300009];
vector<pii> jobs[300009];
vector<int> g[300009];
void dfs(int u){
    for(int v : g[u]){
        dfs(v);
        if(jobs[u].size() < jobs[v].size()) swap(jobs[u], jobs[v]);
        for(pii job : jobs[v]){
            jobs[u].pb({job.fi + x[u], min(x[u], job.se + x[u])});
        }
    }
    jobs[u].pb({x[u], x[u]});
    int ma = -1e18;
    for(pii job : jobs[u]){
        if(job.fi > 0){
            ma = max(ma, job.se);
        }
    }
    cost[u] = ma;
    return;
}
signed main() {
    if (fopen(taskname".inp","r")) {
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++){
        int p;
        cin >> x[i] >> p;
        g[p].pb(i);
    }
    dfs(0);
    priority_queue<pii> pq;
    pq.push({0, 0});
    int profit = s;
    while(!pq.empty()){
        pii u = pq.top();
        pq.pop();
        if(profit + u.fi < 0) break;
        profit += x[u.se];
        for(int v : g[u.se]){
            pq.push({cost[v], v});
        }
    }
    cout << profit - s;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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