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.

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.

Thank you for the reply.

I thought i was just sending the pointer. I didn't knew it copies the array. I'll try this

Update: It didn't work. submission

Ohh sorry I didn't read it carefully.

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

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. Submission

What I don't understand is how this solution exceeds the memory limit.