[help] Doubt about memory complexity in IOI 2010 Traffic Solution

Revision en1, by Lakshi4h, 2021-03-05 06:09:28

Today I wrote a solution for IOI 2010 Traffic

But It exceeds the memory limit.

code

Graph is a tree and has $$$n$$$ $$$(<1e6)$$$ nodes. Therefore i think the total memory will be

  • $$$n$$$ for array p

  • $$$n$$$ each for s and d arrays

  • $$$2*(n-1)$$$ for adjacency vector

  • $$$2*(n-1)$$$ for map m

Complexity is $$$O(n)$$$

But how does this exceeds 250MB? Can someone point me to my mistake.

Thank you.

Tags help, ioi, mle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Lakshi4h 2021-03-05 06:09:28 1534 Initial revision (published)