Submission #1191358

#TimeUsernameProblemLanguageResultExecution timeMemory
1191358DedibeatJobs (BOI24_jobs)C++20
0 / 100
28 ms12844 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define F first #define S second template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "(" << p.F << "," << p.S << ")"; } template<typename T> void print(T v) { for(auto x : v) cout << x << " "; cout << "\n"; } int w[300005]; int p[300005]; vector<int> adj[300005]; int main() { ll n, s; cin >> n; ll sum = 0, mx = s; for(int i = 1; i <= n; i++) { cin >> w[i] >> p[i]; adj[p[i]].push_back(i); sum += w[i]; } using node = pair<int, int>; priority_queue<node, vector<node>, greater<>> q; for(int i = 1; i <= n; i++) { if(adj[i].size() == 0) q.emplace(w[i], i); } while(!q.empty()) { mx = max(mx, sum); auto [cost, i] = q.top(); q.pop(); sum -= cost; if(p[i] != 0) { q.emplace(w[p[i]], p[i]); } } cout << mx << "\n"; }
#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...