Submission #1124164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124164		mychecksedad	Jobs (BOI24_jobs)	C++17	100 / 100	239 ms	115308 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n; ll s, a[N], dp[N], sum[N];
vector<int> g[N], R;
vector<pair<ll, ll>> T[N];
void dfs(int v){
  dp[v] = a[v];
  sum[v] = a[v];
  priority_queue<array<ll, 3>> Q;
  for(int u: g[v]){
    dfs(u);
    if(sum[u] >= 0){
      Q.push({
        dp[u], a[u], u
      });
    }
    // for(auto p: T[u]) T[v].pb(p);
  }
  while(!Q.empty() && sum[v] < 0){
    auto p = Q.top(); Q.pop();
    sum[v] += p[1];
    dp[v] = min(dp[v], sum[v]);
  
    for(int u: g[p[2]]){
      if(sum[u] >= 0)
        Q.push({dp[u], a[u], u});
    }
  }
  // for(int i = 0; i < T[v].size() && sum < 0; ++i){
  //   sum += T[v][i].ss;
  //   dp[v] = min(dp[v], sum);
  // }
  // if(sum >= 0){
  //   T[v].pb({-dp[v], a[v]});
  // }
  // cout << v <<  ' ' << dp[v] << '\n';
}
void solve(){
  cin >> n >> s;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    int p; cin >> p;
    g[p].pb(i);
    if(p==0) R.pb(i);
  }
  priority_queue<array<ll, 3>> Q;
  for(int r: R){
    dfs(r);
    if(sum[r] >= 0){
      Q.push({
        dp[r], a[r], r
      });
    }
    // for(auto p: T[u]) T[v].pb(p);
  }
  ll ans = s, cur = s;
  while(!Q.empty()){
    auto p = Q.top(); Q.pop();
    if(cur + p[1] < 0) break;
    // cout << p[2] << ' ';  
    cur += p[1];
    ans=max(ans, cur);
    for(int u: g[p[2]]){
      if(sum[u] >= 0){
        Q.push({dp[u], a[u], u});
      }
    }
  }
  cout << ans - s;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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