Submission #1262141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262141		huutuan	Jobs (BOI24_jobs)	C++17	100 / 100	242 ms	71868 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=3e5+10;
int n, s, p[N], x[N];
vector<int> g[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq[N];

void dfs(int u){
   for (int v:g[u]){
      dfs(v);
      if (pq[u].size()<pq[v].size()) pq[u].swap(pq[v]);
      while (pq[v].size()) pq[u].push(pq[v].top()), pq[v].pop();
   }
   if (x[u]>=0) pq[u].emplace(0, x[u]);
   else{
      int need=-x[u], pf=-x[u];
      while (need && pq[u].size()){
         auto t=pq[u].top(); pq[u].pop();
         int m=min(need, t.second);
         pf=max(pf, need+t.first);
         need-=m; t.second-=m;
         if (t.second) pq[u].push(t);
      }
      if (need) return;
      int sum=0;
      while (pq[u].size() && pq[u].top().first<=pf){
         sum+=pq[u].top().second;
         pq[u].pop();
      }
      pq[u].emplace(pf, sum);
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> s;
   for (int i=1; i<=n; ++i){
      cin >> x[i] >> p[i];
      g[p[i]].push_back(i);
   }
   dfs(0);
   int cur=s;
   while (pq[0].size() && cur>=pq[0].top().first){
      cur+=pq[0].top().second;
      pq[0].pop();
   }
   cout << cur-s << '\n';
   return 0;
}

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