Submission #993596

#	Time	Username	Problem	Language	Result	Execution time	Memory
993596		AlperenT_	Jobs (BOI24_jobs)	C++17	100 / 100	302 ms	79188 KiB

Main

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 1e18  , maxk = 2022  , mod =1e9 + 7;
multiset <pii> s[maxn] ;
int a[maxn] ;
vector <int> G[maxn] ; 

void dfs(int v){
  for(int u : G[v]){
    dfs(u);
    if(sz(s[u]) > sz(s[v])){
      swap(s[v]  , s[u]) ;
    }
    while(sz(s[u])){
      auto a = s[u].begin() ;
      s[v].insert((*a));
      s[u].erase(a);
    }  
  }
  int m1 = min(0ll,a[v]) , sm = a[v] ;
  if(sm < 0)
  while(sz(s[v])){
    auto a = *s[v].begin() ;
    m1 = min(m1 , sm-a.F) ;
    sm += a.S ;
    s[v].erase(s[v].begin());
    if(sm > 0){
      break ;
    }
  }
  if(sm > 0){
    while(sz(s[v])){
      auto a = (*s[v].begin()) ;
      if((-a.F) < m1){
        break ;
      }
      sm += a.S ; 
      s[v].erase(s[v].begin()) ;
    } 
    s[v].insert({-m1 , sm});
  }
  
}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);   
  int n , x ;
  cin >> n >> x ; 
  int k = x; 
  rep(i , 1, n){
    int p ;
    cin >> a[i] >> p ;
    G[p].pb(i);
  }
  dfs(0) ;
  while(sz(s[0])){
    auto a = (*s[0].begin()) ;
    if(x-a.F < 0){
      break ;
    }
    x += a.S ;
    s[0].erase(s[0].begin()) ;
  }
  cout << x - k<< "\n" ; 
}

/*

*/

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