fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef vector<int> vi;
  6. typedef long long ll;
  7. typedef pair<int,int> pi;
  8. typedef pair<int,int> pii;
  9. typedef long double ld;
  10. typedef complex<ld> cd;
  11. typedef pair<ll,ll> pl;
  12. typedef vector<pi> vpi;
  13.  
  14. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  15. #define F0R(i,a) FOR(i,0,a)
  16. #define R0F(i,a) for (int i = (a)-1; i >= 0; --i)
  17. #define sz(a) (int)a.size()
  18. #define rep(i, a, b) for(int i = (a); i < (b); ++i)
  19. #define trav(a, x) for(auto& a : x)
  20. #define all(x) x.begin(), x.end()
  21. #define pb push_back
  22.  
  23. #define f first
  24. #define s second
  25.  
  26. const int MX = 200005;
  27. const ll INF = 1e18;
  28.  
  29. template<class T> void ckmax(T& a, T b) { a = max(a,b); }
  30. template<class T> void ckmin(T& a, T b) { a = min(a,b); }
  31.  
  32. int n;
  33. vpi adj[MX];
  34. ll mn[MX];
  35. int X[MX], root = 0;
  36. ll minAns = 0;
  37. bool special[MX];
  38.  
  39. void addEdge(int a, int b, int c) {
  40.     adj[a].pb({b,c});
  41.     adj[b].pb({a,c});
  42. }
  43.  
  44. void dfsw(int x, int y) {
  45.     special[x] = x == 0;
  46.     ll ret = 0;
  47.     int cool = -1;
  48.     trav(t,adj[x]) if (t.f != y) {
  49.         dfsw(t.f,x);
  50.         special[x] |= special[t.f];
  51.         if (!special[t.f]) ret += min(1LL-t.s,mn[t.f]-t.s);
  52.         else ret += mn[t.f]-t.s;
  53.     } else cool = t.s;
  54.     if (x != root) {
  55.         assert(cool != -1);
  56.         mn[x] = ret+X[x];
  57.         ckmin(minAns,mn[x]-cool);
  58.     }
  59. }
  60.  
  61. ll worst() {
  62.     dfsw(root,-1);
  63.     return -minAns;
  64. }
  65.  
  66. priority_queue<pi> stor[MX]; 
  67. // stores pairs in the form (a,b) where b >= 0, in decreasing order of a
  68.  
  69. // suppose that you currently have cur dollars
  70. // then using this pair means that cur -> cur+a -> cur+b
  71. // if a is negative, think of this as going into debt while entering a subtree 
  72. // in order to gain money after you exit a subtree
  73.  
  74. // if you have a bunch of pairs in these form, then in order to gain as much profit
  75. // as possible while minimizing the amount you go into debt, you should take the pairs
  76. // with greater a first
  77.  
  78. pi operator+(const pi& l, const pi& r) { // if you use pair l and then pair r
  79.     return {min(l.f,l.s+r.f),l.s+r.s};
  80. }
  81.  
  82. void adjust(priority_queue<pi>& a, int x) {
  83.     assert(x < 0); pi p = {x,x};
  84.     while (sz(a) && (p.s <= 0 || a.top().f >= p.f)) { 
  85.     	// don't want to put an element in priority queue if it's second element is <= 0
  86.     	// (you wouldn't want to enter a subtree if it gives non-positive overall profit)
  87.     	// so keep popping from priority queue and modifying p until p.s > 0
  88.         auto t = a.top(); a.pop();
  89.         p = p+t;
  90.     }
  91.     if (p.s > 0) a.push(p); 
  92.     // if p.s <= 0, then definitely no point in entering subtree corresponding to a
  93. }
  94.  
  95. void comb(priority_queue<pi>& a, priority_queue<pi>& b) { 
  96. 	// merge two pqs in O(S*logS) where S is size of smaller one
  97.     if (sz(a) < sz(b)) swap(a,b);
  98.     while (sz(b)) { a.push(b.top()); b.pop(); }
  99. }
  100.  
  101. void yay(int x, int y) { // great function name!
  102.     trav(t,adj[x]) if (t.f != y) {
  103.         yay(t.f,x); 
  104.         adjust(stor[t.f],-t.s); // adjust elements in pq cost of edge
  105.     } 
  106.     stor[x].push({X[x],X[x]});
  107.     trav(t,adj[x]) if (t.f != y) comb(stor[x],stor[t.f]);
  108. }
  109.  
  110. ll best() {
  111.     X[root] = 1e9; yay(0,-1); // set value of motherlode = INF
  112.     int ans = 0, cur = 0;
  113.     while (sz(stor[0]) && ans < 1e9/2) { // you can stop once you reach the motherlode
  114.     	// (initial amount of money)+cur+stor[0].top().f must be at least 0
  115.     	ckmax(ans,-cur-stor[0].top().f); cur += stor[0].top().s;
  116.     	stor[0].pop();
  117.     }
  118.     return ans;
  119. }
  120.  
  121. int main() {
  122.     ios_base::sync_with_stdio(0); cin.tie(0);
  123.     cin >> n;
  124.     FOR(i,1,n) {
  125.         int p,y; cin >> p >> X[i] >> y;
  126.         addEdge(i,p,y);
  127.     }
  128.     while (X[root] != -1) root ++;
  129.     cout << worst() << " " << best();
  130. }
Success #stdin #stdout 0s 14496KB
comments (?)
stdin
copy 
5
0 3 1
0 0 2
2 -1 1
2 0 5
stdout
copy 
8 1
https://ideone.com/2IU9yF
Prospecting (Public)
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!