Submission #1022031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022031		huutuan	Jobs (BOI24_jobs)	C++14	54 / 100	2089 ms	38484 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>

using namespace std;

// #define int long long
using ll=long long;

const int N=3e5+10;
int n, p[N];
ll s, a[N];
ll f[N], pf[N];
vector<int> g[N];
// vector<int> tr;

void dfs(int u, ll sum){
   sum+=a[u];
   pf[u]=min(pf[p[u]], sum);
   for (int v:g[u]) dfs(v, sum);
   f[u]=(s+pf[u]<0?0:a[u]);
   for (int v:g[u]) f[u]+=f[v];
   f[u]=max(0ll, f[u]);
}

void trace(int u){
   if (s+pf[u]<0){
      // tr.push_back(u);
      return;
   }
   ll sum=a[u];
   for (int v:g[u]) sum+=f[v];
   if (f[u]==sum){
      a[u]=0;
      for (int v:g[u]) trace(v);
   }// else tr.push_back(u);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> s;
   for (int i=1; i<=n; ++i){
      cin >> a[i] >> p[i];
      g[p[i]].push_back(i);
   }
   ll ans=0;
   for (int i=1; i<=n; ++i){
      dfs(0, 0);
      ans+=f[0];
      s+=f[0];
      trace(0);
      if (!f[0]) break;
      // g[0].swap(tr);
      // tr.clear();
   }
   cout << ans << '\n';
   return 0;
}

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