Submission #1266073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266073		veluca93	Towns (IOI15_towns)	C++20	25 / 100	9 ms	328 KiB

towns

#include "towns.h"
#include <algorithm>
#include <limits>
#include <vector>

int hubDistance(int N, int) {
  std::vector<int> distances_from_0(N);

  for (int i = 1; i < N; i++) {
    distances_from_0[i] = getDistance(0, i);
  }

  int u = std::max_element(distances_from_0.begin(), distances_from_0.end()) -
          distances_from_0.begin();

  std::vector<int> distances_from_u(N);
  distances_from_u[0] = distances_from_0[u];

  for (int i = 1; i < N; i++) {
    if (i == u)
      continue;
    distances_from_u[i] = getDistance(u, i);
  }

  int v = std::max_element(distances_from_u.begin(), distances_from_u.end()) -
          distances_from_u.begin();

  int diameter = distances_from_u[v];

  // y = connection point from [i] to 0u path.
  std::vector<int> distance_y_to_u(N);
  for (int i = 0; i < N; i++) {
    distance_y_to_u[i] =
        (distances_from_u[i] + distances_from_0[u] - distances_from_0[i]) / 2;
  }

  int radius = std::numeric_limits<int>::max();

  for (int i = 0; i < N; i++) {
    // if both on 0u and vu path
    if (distance_y_to_u[i] <= distance_y_to_u[v]) {
      int r = std::max(distance_y_to_u[i], diameter - distance_y_to_u[i]);
      if (r < radius)
        radius = r;
    }
  }

  return radius;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39