-1

Why does my code give this bad_alloc error, even though I have allocated enough memory? I'm not able to figure it out.

this is the problem link

Passing by reference did not resolve the error.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

void dfs(ll root , vector<vector<ll>> &graph , vector<ll> &weights , ll max_weight , ll &ans)
{
    for(auto adj : graph[root])
    {
        ans = max(ans , (max_weight - weights[adj]) );
        max_weight = max( max_weight , weight[adj]);
        dfs(adj , graph , weights , max_weight , ans);
    }
}

int main() {
    ll n;
    cin>>n;
    vector<ll>a(n+1 , 0);
    vector<vector<ll>>v(n+1);
    
    for(ll i=0 ;i<n;i++)
        {
            ll wt;cin>>wt;a[i]=wt;
        }
    ll root = -1;
    for(ll i=0 ;i<n;i++)
    {
        ll p;cin>>p;
        if(p == -1)root = i;
        v[p-1].push_back(i);
    }
    
    ll ans = INT_MIN;
    ll wt = a[root];
    dfs(root , v , a , wt , ans);
    cout<<ans<<endl;
    
    return 0;
}
Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Ananyeah.
  • 3
  • 3
  • before asking others to read your code you should get rid of all this unecessary obfuscation. What is `ll` ? Why do most variables have meaningless 1-2 letter names? `for(auto it : graph[root])` here the name suggests `it` would be an iterator but it isnt. Actually the [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) is the least of all evil here. – 463035818_is_not_an_ai Nov 08 '22 at 13:37
  • You should use a debugger to find out where the exception is thrown, but I would do a wild guess and say that it is not a good idea, to have a recursive function on a graph and copy the graph at each invocation. – gerum Nov 08 '22 at 13:38
  • 1
    *i'm not able to figure it out* -- Stop using competivie coding websites as a way to learn basic C++. By using such websites, all you learn are bad habits, and you miss beginner-level topics on C++. The errors are obvious -- things like passing-by-value instead of by reference. A C++ programmer who has learned C++ properly would *never* make that mistake. – PaulMcKenzie Nov 08 '22 at 14:03
  • `ll p;cin>>p; if(p == -1)root = i; v[p-1].push_back(i);` looks very odd. When `p == -1` then `v[p-1]` will crash. – mch Nov 08 '22 at 14:08

1 Answers1

0

dfs takes a copy of the vectors graph and a every time it is called recursively, and this probably exhausts your memory.

Pass references instead:

  void dfs(ll root , vector<vector<ll>> const &graph , vector<ll> const &a , ll wt , ll &ans)

As a side note: is there a reason you return the result in a reference parameter instead of a return value? To my mind it would be more natural to use

  ll dfs(ll root , vector<vector<ll>> const &graph , vector<ll> const &a , ll wt)

and return ans from dfs.

Wintermute
  • 42,983
  • 5
  • 77
  • 80
  • i tried passing by reference and it still throws the same error , and thanks for your suggestions. – Ananyeah. Nov 08 '22 at 14:54
  • The for loop still takes a copy of a vector (because you use auto instead of auto&), that's probably the allocation that throws. You can check this with a debugger. Also, I think your recursive function does not have a stop condition. So you're recursing endlessly and allocating memory in each recursion; at some point you just run out of memory. Run the code in a debugger, I'd wager your call stack is extremely deep by the time the error happens. – Wintermute Nov 08 '22 at 15:54