Блог пользователя MDantas

Автор MDantas, 11 лет назад, По-английски

Hey everyone, I'm solving one of the problems from IOI 2012 ( Ideal City ). I think I've got the whole idea, but my code seems to have some bug as it's not giving the expected output for some cases. I'm not so sure but my guess is that the bug is on the function to calculate the sum between every pair of nodes on a tree, so what I'm asking is if someone knows a specific problem where I can test my function to calculate the sum between every pair of nodes on a tree. If no one knows it, it'd be just good if someone gives me implementation for this specific problem so I can check if mine is correct or near it.

Thanks!

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The link below is official website of IOI2012 and it has given hints for the problem Ideal City.

Hints for Tasks of IOI2012

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You did not understand me. I know how to solve it and I've already coded it, but it has some bug and I don't know where it is. I've a guess that the bug is on the function to calculate the sum between every pair of node on a weighted tree, but I don't know how to test it. So what I'm asking is if some of you guys knows any problem about it.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This snippet should work.

The gist of it is:

  struct Answer{
    ll path_sum;   // sum of all (? -> X) paths toward root
    ll path_count; // quantity of """""""""""""""""""""""""
    ll total;      // answer for subtree rooted at X
  };

  Answer dfs(int x){
    Answer res={0,1,0};

    for (auto e: edge[x]){
      auto rec=dfs(e.id);
      rec.path_sum += e.weight * rec.path_count;

      res = {
        res.path_sum + rec.path_sum,
        res.path_count + rec.path_count,
        res.total + rec.path_sum * res.path_count + rec.total + res.path_sum * rec.path_count
      };
    }
    return res;
  }
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you. That's exactly what I was looking for. BTW, the main idea is the same as mine an so the implementation, so I guess the bug is not on this function. Thank you again