제출 #1047727

#제출 시각아이디문제언어결과실행 시간메모리
1047727raczekJobs (BOI24_jobs)C++17
14 / 100
2070 ms23028 KiB
#include<bits/stdc++.h> using namespace std; #ifdef DEBUG auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";} auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";} #define debug(X) cerr<<"["#X"]: "<<X<<endl; #else #define debug(X) {} #endif #define int long long int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, s; cin>>n>>s; int org = s; vector<vector<int> > graph(n+1); vector<int> cost(n+1); vector<bool> deg(n+1, true); for(int i=1;i<=n;i++) { int p, c; cin>>c>>p; cost[i] = c; if(p == 0) deg[i] = false; else graph[p].push_back(i); } function<int(int, int, bool)> dfs = [&](int a, int bal, bool f) { bal += cost[a]; if(bal < 0) return (int)-1; vector<pair<int, int> > paths; paths.push_back({0, a}); for(auto v : graph[a]) paths.push_back({dfs(v, bal, false), v}); sort(paths.begin(), paths.end()); if(f) { deg[a] = true; for(auto v : graph[a]) deg[v] = false; if(paths.back().second != a) dfs(paths.back().second, bal, true); } return (int)(paths.back().first + cost[a]); }; while(true) { vector<pair<int, int> > paths; for(int i=1;i<=n;i++) if(deg[i] == false) paths.push_back({dfs(i, s, false), i}); if(paths.size() == 0) break; sort(paths.begin(), paths.end()); if(paths.back().first > 0) {dfs(paths.back().second, s, true); s += paths.back().first;} else break; } cout<<s-org; }
#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...