lazywitt's blog

little doubt regarding memory.
By lazywitt, history, 4 years ago, In English

when a problem says, memory limit : 256 MB. Does it stands for : every test case 256 MB or memory of sum of all testcases : 256 MB.

reason to ask : https://codeforces.me/contest/1472/submission/103587221

no way , i get MLE for test case 10 which has 121 vertices and 180 edges, while i passed 200000 vertices and 199999 edges case i.e test case 9 .

Any associated insight is much appreciated. Thanks in advance.

Tags mle
  • Vote: I like it
  • -15
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Note that here

for( auto i: vec ){
    for( auto j :  g[i] ){
        if( !vis[j] ) temp.push_back( j );

you don't guarantee that the same j will not be added for each i. So imagine a part of the graph with several layers of 5 vertices in each layer, and each 5 in each layer are connected with each 5 in the next layer (total of 25 vertices and 100 edges). If 5 vertices from the first layer are in your vec, you will add j to temp 25 times. Next time you will iterate over 25 vertices (each will be encountered 5 times in vec), and add 125 times to temp (each vertex will be encountered 25 times), and so on, growing exponentially. Just add vis[j] = 1 together with temp.push_back(j), and it will do it. But better implement bfs with a queue or two-pointer array, you are doing a lot of expensive operations in this implementation.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i feel so stupid now :(, I highly appreciate the help man. Thanks.

    → Reply