Submission #102717

#	Time	Username	Problem	Language	Result	Execution time	Memory
102717		wxh010910	Towns (IOI15_towns)	C++17	100 / 100	33 ms	1144 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

int hubDistance(int N, int sub) {
  vector<vector<int>> dist(2, vector<int>(N, 0));
  int root = 0, left = 0, right = 0;
  for (int i = 0; i < N; ++i) {
    if (i != root) {
      dist[0][i] = getDistance(root, i);
      if (dist[0][i] > dist[0][left]) {
        left = i;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    if (i != left) {
      dist[1][i] = getDistance(left, i);
      if (dist[1][i] > dist[1][right]) {
        right = i;
      }
    }
  }
  int limit = (dist[0][left] - dist[0][right] + dist[1][right]) >> 1;
  vector<int> from(N, 0), all;
  for (int i = 0; i < N; ++i) {
    from[i] = (dist[1][i] - dist[0][i] + dist[0][left]) >> 1;
    if (from[i] <= limit) {
      all.push_back(from[i]);
    }
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  int ans = dist[1][right];
  for (auto p : all) {
    ans = min(ans, max(p, dist[1][right] - p));
  }
  int another = root = -1;
  for (auto p : all) {
    if (max(p, dist[1][right] - p) == ans) {
      if (root == -1) {
        root = p;
      } else {
        another = p;
      }
    }
  }
  if (root != -1 && another != -1) {
    int size_left = 0;
    for (int i = 0; i < N; ++i) {
      if (from[i] <= root) {
        ++size_left;
      }
    }
    if (size_left == N - size_left) {
      return ans;
    } else if (size_left < N - size_left) {
      root = another;
    }
  }
  int last = -1, cur = 0;
  auto is_same = [&](int x, int y) {
    if (from[x] == root && from[y] == root) {
      return dist[0][x] + dist[1][y] > getDistance(x, y) + dist[0][left];
    } else {
      return (from[x] < root && from[y] < root) || (from[x] > root && from[y] > root);
    }
  };
  vector<int> type(N);
  for (int i = 0; i < N; ++i) {
    if (!cur) {
      last = i;
      ++cur;
      type[i] = 0;
    } else if (is_same(i, last)) {
      ++cur;
      type[i] = 1;
    } else {
      --cur;
      type[i] = 2;
    }
  }
  if (!cur) {
    return ans;
  }
  int best = last, total = cur = 0;
  bool same = false;
  for (int i = 0; i < N; ++i) {
    if (!type[i]) {
      if (is_same(best, i)) {
        same = true;
        ++total;
      }
      ++cur;
    } else if (type[i] == 1) {
      if (same) {
        ++total;
      }
      ++cur;
    } else {
      if (is_same(best, i)) {
        ++total;
      }
      if (!--cur) {
        same = false;
      }
    }
  }
  if (total > N >> 1) {
    return -ans;
  } else {
    return ans;
  }
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

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