제출 #1025490

#제출 시각아이디문제언어결과실행 시간메모리
1025490pccJobs (BOI24_jobs)C++17
11 / 100
275 ms68852 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fs first #define sc second const ll mxn = 3e5+10; ll N,S; ll arr[mxn]; vector<int> tree[mxn],tree2[mxn],tree3[mxn]; vector<int> rts; ll dp[mxn]; priority_queue<pll,vector<pll>,less<pll>> son[mxn]; ll shift[mxn]; ll dist[mxn]; void dfs(int now,int top = 0){ dp[top] += arr[now]; for(auto nxt:tree[now]){ if(arr[nxt]<0){ dist[nxt] = dist[top]+arr[nxt]; tree2[top].push_back(nxt); dfs(nxt,nxt); } else{ dfs(nxt,top); } } } void dfs2(int now){ for(auto nxt:tree2[now]){ dfs2(nxt); //cerr<<"TREE2: "<<now<<','<<nxt<<':'<<arr[nxt]<<' '<<dp[nxt]<<endl; son[now].push(pll(arr[nxt],nxt)); } ll tmp = arr[now]; while(dp[now]<=0&&!son[now].empty()){ auto [dep,tar] = son[now].top();son[now].pop(); if(dp[tar]<0)continue; arr[now] = min(arr[now],shift[now]+dep+arr[now]); dp[now] += dp[tar]; if(son[now].size()>=son[tar].size()){ while(!son[tar].empty()){ auto [tval,nxt] = son[tar].top(); son[tar].pop(); son[now].push(pll(tval+shift[tar]-shift[now]+arr[tar],nxt)); } } else{ son[now].swap(son[tar]); swap(shift[now],shift[tar]); shift[now] += arr[tar]; while(!son[tar].empty()){ auto [tval,nxt] = son[tar].top(); son[tar].pop(); son[now].push(pll(tval+shift[tar]-shift[now],nxt)); } } } return; return; } void dfs3(int now){ //cerr<<now<<":"<<arr[now]<<','<<dp[now]<<endl; for(auto nxt:tree3[now]){ //cerr<<now<<','<<nxt<<endl; dfs3(nxt); } return; } priority_queue<pll,vector<pll>,less<pll>> pq; int main(){ cin>>N>>S; for(int i = 1;i<=N;i++){ ll x,p; cin>>x>>p; tree[p].push_back(i); arr[i] = x; } dfs(0,0); //cerr<<"DFS1 DONE!"<<endl; dfs2(0); //cerr<<"DFS2 DONE!"<<endl; pq.push(pll(arr[0],0)); ll ans = 0; while(!pq.empty()&&S+pq.top().fs>=0){ auto [val,id] = pq.top();pq.pop(); if(dp[id]<0)continue; ans += dp[id]; S += dp[id]; while(!son[id].empty()){ auto [__,nxt] = son[id].top(); son[id].pop(); pq.push(pll(arr[nxt],nxt)); } } cout<<ans<<'\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void dfs2(int)':
Main.cpp:39:5: warning: unused variable 'tmp' [-Wunused-variable]
   39 |  ll tmp = arr[now];
      |     ^~~
#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...