제출 #1080309

#제출 시각아이디문제언어결과실행 시간메모리
1080309someoneJobs (BOI24_jobs)C++14
0 / 100
2065 ms39940 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define all(x) x.begin(), x.end() using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using namespace std; const int N = 3e5 + 42; struct Node { i64 i, sub, add, gain; bool operator <(const Node& other) const { if(max(sub, other.sub - gain) == max(other.sub, sub - other.gain)) return i < other.i; return max(sub, other.sub - gain) < max(other.sub, sub - other.gain); } }; int par[N]; int F(int i) { if(par[i] == i) return i; return par[i] = F(par[i]); } void U(int a, int b) { a = F(a), b = F(b); par[b] = a; } Node merge(Node a, Node b) { Node ans; ans.i = a.i; ans.sub = max(a.sub, b.sub - a.gain); ans.gain = a.gain + b.gain; ans.add = ans.gain + ans.sub; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; i64 s; cin >> s; set<Node> pq; vector<int> p(n+1); vector<Node> node(n+1); for(int i = 1; i <= n; i++) { node[i].i = i; par[i] = i; i64 x; cin >> x >> p[i]; node[i].gain = x; if(x < 0) { node[i].sub = -x, node[i].add = 0; } else { node[i].add = x, node[i].sub = 0; } pq.insert(node[i]); } while(!pq.empty()) { auto it = pq.begin(); Node x = *it; Node fus = merge(node[F(p[x.i])], x); if(!(F(p[x.i]) == 0 && (fus.sub > s || x.gain < 0))) { U(p[x.i], x.i); pq.erase(x); if(F(p[x.i]) != 0) { pq.erase(node[F(p[x.i])]); pq.insert(fus); } node[F(p[x.i])] = fus; } else { pq.erase(x); } } cout << max(0ll, node[0].gain) << '\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...