제출 #1266090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266090		veluca93	도시들 (IOI15_towns)	C++20	100 / 100	11 ms	456 KiB

towns

#include "towns.h"
#include <algorithm>
#include <cassert>
#include <limits>
#include <stdio.h>
#include <utility>
#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;
    }
  }

  int max_size = N / 2;

  int distance_center_u = -1;
  int distance_other_center_u = -1;

  for (int i = 0; i < N; i++) {
    int dist = distance_y_to_u[i];
    if (dist == radius)
      distance_center_u = dist;
    else if (dist == diameter - radius)
      distance_other_center_u = dist;
  }

  if (distance_center_u == -1) {
    distance_center_u = distance_other_center_u;
  } else if (distance_other_center_u != -1) {
    assert(distance_center_u > distance_other_center_u);
    int subtree_size_center = 0;
    for (int i = 0; i < N; i++) {
      if (distance_y_to_u[i] >= distance_center_u) {
        subtree_size_center++;
      }
    }
    if (subtree_size_center * 2 == N) {
      return radius;
    } else if (subtree_size_center * 2 < N) {
      distance_center_u = distance_other_center_u;
    }
  }

  // From here on, distance_center_u is the only possible candidate.

  std::vector<int> connected_to_x;
  int connected_before_x = 0;
  int connected_after_x = 0;

  for (int i = 0; i < N; i++) {
    if (distance_y_to_u[i] < distance_center_u) {
      connected_before_x++;
    } else if (distance_y_to_u[i] > distance_center_u) {
      connected_after_x++;
    } else {
      connected_to_x.push_back(i);
    }
  }

  if (connected_before_x > max_size || connected_after_x > max_size) {
    return -radius;
  }

  auto are_connected_with_same_edge = [&](int a, int b) {
    int a_from_center = distances_from_u[a] - distance_y_to_u[a];
    int b_from_center = distances_from_u[b] - distance_y_to_u[b];
    assert(a_from_center > 0);
    assert(b_from_center > 0);
    int dist = getDistance(a, b);
    assert(dist <= a_from_center + b_from_center);
    return dist != a_from_center + b_from_center;
  };

  std::vector<std::vector<int>> bags;
  std::vector<std::vector<int>> dead_bags;
  for (auto z : connected_to_x) {
    bags.push_back({z});
  }

  while (bags.size() > 1) {
    std::vector<std::vector<int>> new_bags;
    if (bags.size() % 2 == 1) {
      new_bags.push_back(bags.back());
      bags.pop_back();
    }
    for (int i = 0; 2 * i < bags.size(); i++) {
      auto bag1 = bags[2 * i];
      auto bag2 = bags[2 * i + 1];
      if (bag1.size() > bag2.size())
        std::swap(bag1, bag2);
      if (are_connected_with_same_edge(bag1[0], bag2[0])) {
        new_bags.push_back(bag1);
        for (auto z : bag2) {
          new_bags.back().push_back(z);
        }
      } else {
        dead_bags.push_back(bag1);
        if (bag1.size() == bag2.size())
          dead_bags.push_back(bag2);
        else
          new_bags.push_back(bag2);
      }
    }
    bags = new_bags;
  }

  if (bags.empty()) {
    return radius;
  }

  assert(bags.size() == 1);

  int largest_subtree_size = bags[0].size();

  for (auto &b : dead_bags) {
    if (are_connected_with_same_edge(b[0], bags[0][0])) {
      largest_subtree_size += b.size();
    }
  }

  // fprintf(stderr, "%d\n", largest_subtree_size);

  return largest_subtree_size > max_size ? -radius : radius;
}

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