tzhamoidin_twink's blog

I need help
By tzhamoidin_twink, history, 21 month(s) ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply