Submission #1203213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203213		abczz	Towns (IOI15_towns)	C++20	0 / 100	9 ms	584 KiB

towns

#include "towns.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long

using namespace std;

ll dist[200][200], X[200], G[200], Z[200], sz[200];
vector <ll> grp;
vector <ll> V[200];
map <ll, ll> mp;
int hubDistance(int N, int sub) {
  grp.clear();
  mp.clear();
  for (int i=0; i<N; ++i) sz[i] = 0;
  ll mx = -1, id = -1, a, b, diam = -1, f = 1e18, hub = -1, hub2 = -1;
	for (int i=1; i<N; ++i) {
    ll res = getDistance(0, i);
    dist[0][i] = dist[i][0] = res;
    if (res > mx) mx = res, id = i;
  }
  a = id;
  for (int i=1; i<N; ++i) {
    if (i == a) continue;
    ll res = getDistance(a, i);
    dist[a][i] = dist[i][a] = res;
    if (res > diam) diam = res, b = i;
  }
  for (int i=1; i<N; ++i) {
    if (i == a) continue;
    ll s = (dist[i][a] + dist[i][0] + dist[0][a]) / 2;
    ++mp[s-dist[i][a]];
    X[i] = s-dist[0][a], G[i] = s-dist[i][a];
  }
  G[0] = 0, G[a] = dist[0][a];
  ++mp[0];
  ++mp[dist[0][a]];
  ll k = 0;
  for (auto [x, y] : mp) {
    mp[x] = k++;
  }
  for (int i=0; i<N; ++i) {
    V[mp[G[i]]].push_back(i);
    Z[mp[G[i]]] = G[i];
  }
  for (int i=0; i<k; ++i) {
    if (Z[i] >= G[b]) {
      Z[i] = dist[0][a]-Z[i];
      if (f > max(Z[i], diam-Z[i])) f = max(Z[i], diam-Z[i]), hub = i, hub2 = -1;
      else if (f == max(Z[i], diam-Z[i])) hub2 = i;
    }
  }
  if (hub2 != -1) {
    ll tot = 0, tot2 = 0;
    for (int i=0; i<=hub; ++i) tot += V[i].size();
    for (int i=hub2; i<N; ++i) tot2 += V[i].size();
    if (tot <= N/2 && tot2 <= N/2) return (int)f;
    else if (tot <= N/2) hub = hub2;
  }
  ll tot = 0, tot2 = 0;
  for (int i=0; i<hub; ++i) tot += V[i].size();
  for (int i=hub+1; i<N; ++i) tot2 += V[i].size();
  if (max(tot, tot2) > N/2) return (int)-f;
  ll cur = -1, x = 0, y = 0;
  for (auto u : V[hub]) {
    if (cur == -1) {
      cur = u, x = 1, y = 0;
      sz[u] = 1;
      grp.push_back(u);
    }
    else {
      ll res = getDistance(cur, u);
      if (res != X[u] + X[cur]) {
        ++x, ++sz[cur];
      }
      else {
        ++y;
        grp.push_back(u);
        sz[u] = 1;
      }
    }
    if (x == y) cur = -1, x = y = 0;
  }
  if (cur == -1) return (int)-f;
  for (auto u : grp) {
    if (cur == u) continue;
    ll res = getDistance(cur, u);
    if (res != X[u] + X[cur]) {
      sz[cur] += sz[u];
    }
  }
  if (sz[cur] > N/2) return (int)-f;
  else return (int)f;
}

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