Submission #994685

#TimeUsernameProblemLanguageResultExecution timeMemory
994685kymJobs (BOI24_jobs)C++14
0 / 100
2068 ms101460 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #ifdef LOCAL void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) #endif const int MAXN = 300005; const int inf=1000000500ll; const long long oo =1000000000000000500ll; const int MOD = (int)1e9+7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int,int> pi; int n,init; int A[MAXN], P[MAXN]; vector<int>child[MAXN]; int lazy[MAXN]; deque<pi> dfs(int x){ deque<pi>dq; for(auto v:child[x]){ deque<pi> dd=dfs(v); for(auto x:dd)dq.push_back(x); } sort(dq.begin(),dq.end()); if(A[x]>=0){ for(auto &v:dq){ v.first-=A[x]; v.first=max(0ll,v.first); } dq.push_front({0ll,A[x]}); } else{ int s=A[x]; while(dq.size() && dq.front().second + s < 0){ s+=dq.front().second; dq.pop_front(); } if(dq.size()){ pi x=dq.front(); x.second+=s; dq.pop_front(); dq.push_front(x); } for(auto &v:dq){ v.first -= A[x]; } } return dq; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> init; for(int i=1;i<=n;i++){ cin>>A[i]>>P[i]; child[P[i]].push_back(i); } deque<pi> dq=dfs(0); int ans=0; while(dq.size() && dq.front().first <= init){ init+=dq.front().second; ans+=dq.front().second; dq.pop_front(); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...