### wOoDeN_sPoOn's blog

By wOoDeN_sPoOn, history, 6 weeks ago,

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.

• +1

 » 6 weeks ago, # |   0 You are creating an array called P several times in dp function and this causes ML.But I guess you don't change anything inside it so I think you don't have to send the array P to the dp function.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 Thank you for the reply.I thought i was just sending the pointer. I didn't knew it copies the array. I'll try thisUpdate: It didn't work. submission
•  » » » 6 weeks ago, # ^ |   0 Ohh sorry I didn't read it carefully.
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 I didn't completely understand your solution but this problem can be solvable like this:1) City is a tree and let node 1 be the root.2) You can dfs the tree and collect sum of fans of subtree of node v in S[v]3) Let i will be the arena then the A[i] is max(S[child[1]], S[child[2]], S[child3]....TotalFan-S[i])4) Answer will be the minimum A[i]Hope this will help you
•  » » » » 6 weeks ago, # ^ |   +1 Thank you.In a fundamental level i guess that is what I'm doing but your solution is way better. I did the same thing like a year ago and got 100 pts. SubmissionWhat I don't understand is how this solution exceeds the memory limit.