fork download
copy 
  1. /*
  2.   SEFI
  3. */
  4.  
  5. #include <set>
  6. #include <vector>
  7. #include <cstdio>
  8. using namespace std;
  9.  
  10.  
  11.  
  12. const int N = 100009;
  13. vector <int> g [ N ];
  14. multiset <int> q[ N ];
  15. int summa[N];
  16.  
  17. int udov [ N ];
  18. int cost [ N ];
  19.  
  20. long long res = 0;
  21. int m;
  22. void add (int &v , int &u){
  23.             multiset <int> &a = q[v];
  24.             multiset <int> &b = q[u];
  25.             if (a.size() < b.size())
  26.               a.swap (b) , swap (summa[v] , summa[u]);
  27.  
  28.             for (multiset <int> ::iterator it = b.begin() ; it != b.end() ; ++it){
  29.                       if (summa[v] + *it <= m)
  30.                       a.insert (*it) , summa[v] += *it;
  31.                       else {
  32.                                 if (!a.empty()&& *it < *(--a.end()))
  33.                                             summa[v] -=*(--a.end()) ,
  34.                                             summa[v] += *it ,
  35.                                             a.erase ((--a.end())) , a.insert (*it);
  36.                       }
  37.             }
  38.             b.clear();
  39. }
  40.  
  41. int n ;
  42.  
  43. void dfs (int v , int p = 0){
  44.       if (cost[v] + summa[v] <= m)
  45.             q[v].insert (cost[v]) , summa[v] += cost[v];
  46.       for (int i = 0 ; i < (int)g[v].size() ; ++i){
  47.                   int to = g[v][i];
  48.                   dfs (to , v);
  49.                   add (v , to);
  50.       }
  51.       res = max (res , (int)q[v].size() * 1LL * udov[v]);
  52. }
  53.  
  54. #define pb push_back
  55.  
  56. int main(){
  57.  
  58.   scanf ("%d%d" , &n , &m);
  59.   for (int i = 1 ; i <= n ; ++i){
  60.               int boss; scanf ("%d%d%d" , &boss , &cost[i] , &udov[i]);
  61.               g[boss].pb(i);
  62.   }
  63.   dfs (1);
  64.   printf ("%lld\n" , res);
  65.  
  66.   return 0;
  67. }
Success #stdin #stdout 0s 7968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YG6Eql
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!