wOoDeN_sPoOn's blog

By wOoDeN_sPoOn, history, 6 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh sorry I didn't read it carefully.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.