Submission #1095266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095266		epicci23	Jobs (BOI24_jobs)	C++17	100 / 100	249 ms	72144 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


const int N = 3e5 + 5;
vector<int> v[N];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq[N];
int par[N],ar[N];

void dfs(int c){
  for(int x:v[c]){
    dfs(x);
    if(sz(pq[c])<sz(pq[x])) swap(pq[c],pq[x]);
    while(!pq[x].empty()){
      pq[c].push(pq[x].top());
      pq[x].pop();
    }
  }
  array<int,2> cur;
  cur[1]=ar[c];
  if(ar[c]<=0) cur[0]=-ar[c];
  else cur[0]=0;
 
  while(!pq[c].empty() && cur[1]<=0){
  	cur[0]=max(cur[0],pq[c].top()[0]-cur[1]);
    cur[1]+=pq[c].top()[1];
    pq[c].pop();
  } 

  while(!pq[c].empty() && cur[0]>=pq[c].top()[0]){
    cur[1]+=pq[c].top()[1];
    pq[c].pop();
  }

  if(cur[1]>0) pq[c].push(cur);
}

void _(){
  int n,s; cin >> n >> s;
  for(int i=1;i<=n;i++){
  	cin >> ar[i] >> par[i];
  	v[par[i]].push_back(i);
  }
  dfs(0);
  int ans=0;
  while(!pq[0].empty() && pq[0].top()[0]<=s+ans){
  	ans+=pq[0].top()[1];
  	pq[0].pop();
  }
  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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