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

Автор tzhamoidin_twink, история, 2 года назад, По-английски

We have unweighted undirected graph with n vertices and m edges (n < 1e5, m < 1e6). You need to find sum of d(u, v) over all pairs of u v, where d(u, v) — minimal distance between u and v.

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

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

I have a certain problem in a previous contest in mind, almost exactly same with this problem, only difference being the constraints for $$$m$$$. Can you please state the source of this problem?

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

    It was on a Belarusian National Olympiad in 2009...

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

      Okay, the problem I was thinking of was "Distance Sum", NERC 2018. The problem was authored by tourist, so he should be able to help better than I can. Good luck on solving the problem.