제출 #1218276

#제출 시각아이디문제언어결과실행 시간메모리
1218276ani5hJobs (BOI24_jobs)C++20
100 / 100
294 ms61452 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct info { ll f, s; bool operator<(const info &o) const { if(f == o.f) return s < o.s; return f < o.f; } bool operator>(const info &o) const { if(f == o.f) return s > o.s; return f > o.f; } }; using ds = priority_queue<info, vector<info>, greater<info>>; void solve() { int n; ll s; cin >> n >> s; ll start = s; vector<ll> c(n + 1); vector<vector<int>> adj(n + 1); for(int i = 1, u; i <= n; i++) { cin >> c[i] >> u; adj[u].push_back(i); adj[i].push_back(u); } auto merge = [&](info &a, info &b) { ll net = a.s - a.f + b.s - b.f; a = {max(a.f, a.f - a.s + b.f), net + max(a.f, a.f - a.s + b.f)}; }; auto dfs = [&](auto &&self, int u, int p) -> ds { ds pq; for(auto &v : adj[u]) if(v != p) { ds re = self(self, v, u); if(re.size() > pq.size()) swap(re, pq); while(re.size() > 0) { pq.push(re.top()); re.pop(); } } info us = {max(-c[u], 0ll), max(c[u], 0ll)}; while(!pq.empty() && (us.s <= us.f || us.s >= pq.top().f)) { auto v = pq.top(); merge(us, v); pq.pop(); } if(us.f < us.s) pq.push(us); return pq; }; ds v = dfs(dfs, 0, -1); while(!v.empty()) { info seg = v.top(); v.pop(); if(s < seg.f) break; s += seg.s - seg.f; } cout << s - start << '\n'; } int main() { int t = 1; // cin >> t; while(t--) solve(); }
#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...