제출 #994628

#제출 시각아이디문제언어결과실행 시간메모리
994628kymJobs (BOI24_jobs)C++14
11 / 100
183 ms58376 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]; void print(priority_queue<pi,vector<pi>,greater<pi>> * pq){ priority_queue<pi,vector<pi>,greater<pi>> cur = *pq; while(cur.size()){ cout << "{ " << cur.top().first << "|"<<cur.top().second<<" } | "; cur.pop(); } } priority_queue<pi,vector<pi>,greater<pi>> * dfs(int x){ priority_queue<pi,vector<pi>,greater<pi>> * pq = new priority_queue<pi,vector<pi>,greater<pi>>(); for(auto v:child[x]){ priority_queue<pi,vector<pi>,greater<pi>> * c = dfs(v); if(c->size() > pq->size())swap(c,pq); while(c->size()){ pq->push(c->top());c->pop(); } } if(A[x]>=0){ pq->push({0,A[x]}); } else{ int s=A[x]; while(s<0 && pq->size()){ if(pq->top().second + s < 0){ s+=pq->top().second; pq->pop(); } else{ pi c=pq->top(); int rem=pq->top().second + s; pq->pop(); pq->push({c.first,rem}); s=0; } } int sum=0; while(pq->size() && pq->top().first < -A[x]){ sum += pq->top().second; pq->pop(); } if(sum){ pq->push({-A[x],sum}); } } //cerr<<x<<":"; //print(pq); //cerr<<endl; return pq; } 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); } priority_queue<pi,vector<pi>,greater<pi>> * pq =dfs(0); int ans=0; while(pq->size() && pq->top().first<=init){ ans += pq->top().second; init += pq->top().second; pq->pop(); } 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...