Submission #238246

#	Time	Username	Problem	Language	Result	Execution time	Memory
238246		rama_pang	Towns (IOI15_towns)	C++14	100 / 100	30 ms	1072 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int hubDistance(int N, int sub) {
  vector<vector<int>> dist(N, vector<int>(N, -1));
  auto Distance = [&](int u, int v) {
    if (u == v) return 0;
    if (dist[u][v] != -1) return dist[u][v];
    return dist[u][v] = dist[v][u] = getDistance(u, v);
  };

  int p = -1, q = -1; // endpoints of tree diameter
  for (int i = 0, mx = -1; i < N; i++) {
    if (Distance(0, i) > mx) {
      mx = Distance(0, i);
      p = i;
    }
  }
  for (int i = 0, mx = -1; i < N; i++) {
    if (Distance(p, i) > mx) {
      mx = Distance(p, i);
      q = i;
    }
  }

  // Hub must lie on diameter and on the path (0, p)
  int R = INT_MAX;
  set<int> hubs;
  for (int i = 0; i < N; i++) {
    int pos = (Distance(0, i) + Distance(0, p) - Distance(p, i)) / 2; 
    // pos = dist(0, x) where x = nearest settlement in path (0, p) from small town i
    if (max(Distance(0, p) - pos, Distance(p, q) - Distance(0, p) + pos) < R) {
      R = max(Distance(0, p) - pos, Distance(p, q) - Distance(0, p) + pos);
      hubs.clear();
      hubs.emplace(pos);
    } else if (max(Distance(0, p) - pos, Distance(p, q) - Distance(0, p) + pos) == R) {
      hubs.emplace(pos);
    }
  }

  int balanced = -1;
  for (auto h : hubs) {
    int l = 0, r = 0, m = 0;
    for (int i = 0; i < N; i++) {
      int pos = (Distance(0, i) + Distance(0, p) - Distance(p, i)) / 2; 
      if (pos < h) l++;
      if (pos > h) r++;
      if (pos == h) m++;
    }
    if (l > N / 2 || r > N / 2) continue; // number of leaves on the side > N / 2
    if (m <= N / 2) {
      balanced = 1;
      break;
    }
    // There are at most 2 hubs, and at most 1 hub with max(l, r) <= N / 2 and
    // m > N / 2. Also, each hub is a large city with degree >= 3.
    // - Both hubs must be adjacent. Assume h2 is on the right of h1. Then if h1 
    //   has max(h1.l, h1.r) <= N / 2 and h1.m > N / 2, that implies 
    //   h1.r = h2.m + h2.r <= N / 2, thus h2.l >= N / 2. To check both h1 and h2, 
    //   h2.l = N / 2. But that means h2.l = h1.m + h1.l = N / 2, while 
    //   h1.m > N / 2, which is a contradiction.

    // To check if there is > N / 2 small towns in same subtree, we can use
    // Boyer-Moore's majority algorithm that which does 3N/2 - 2 comparisons,
    // described at http://www.cs.yale.edu/publications/techreports/tr252.pdf.

    vector<int> bucket; // the current majority
    vector<int> ls; // all adjacent elements have different subtrees

    auto SameSubtree = [&](int u, int v) {
      int pos_u = (Distance(0, u) + Distance(0, p) - Distance(p, u)) / 2;
      int pos_v = (Distance(0, v) + Distance(0, p) - Distance(p, v)) / 2;
      if (pos_u != h || pos_v != h) return false;
      int u_to_hub = (Distance(0, u) + Distance(p, u) - Distance(0, p)) / 2;
      int v_to_hub = (Distance(0, v) + Distance(p, v) - Distance(0, p)) / 2;
      return u_to_hub + v_to_hub != Distance(u, v);
    };

    for (int v = 0; v < N; v++) {
      if (ls.empty() || !SameSubtree(ls.back(), v)) {
        ls.emplace_back(v);
        if (!bucket.empty()) {
          ls.emplace_back(bucket.back());
          bucket.pop_back();
        }
      } else {
        bucket.emplace_back(v);
      }
    }
    
    int T = ls.back(); // the majority, if it exists
    while (!ls.empty()) {
      if (SameSubtree(T, ls.back())) { // last 2 elements on the list is different
        if (ls.size() >= 2) {
          ls.pop_back();
          ls.pop_back();
        } else {
          bucket.emplace_back(ls.back());
          ls.pop_back();
        }
      } else {
        if (bucket.empty()) break;
        ls.pop_back();
        bucket.pop_back();
      }
    }
    if (bucket.empty()) { // no majority exists
      balanced = 1;
    }
  }

  return R * balanced;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:5: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