Submission #97039

#	Time	Username	Problem	Language	Result	Execution time	Memory
97039		tincamatei	Towns (IOI15_towns)	C++14	100 / 100	55 ms	5016 KiB

towns

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

using namespace std;

const int MAX_N = 110;
const int MAX_DIST = 1000000;

struct QueryStuff {
  int rem;
  int matr[MAX_N][MAX_N];
  QueryStuff(int n) {
    for(int i = 0; i < MAX_N; ++i)
      for(int j = 0; j < MAX_N; ++j)
        matr[i][j] = -1;
    for(int i = 0; i < MAX_N; ++i)
      matr[i][i] = 0;
    rem = n * (n - 1) / 2;
  }

  int dist(int a, int b) {
    if(matr[a][b] == -1) {
      assert(rem > 0);
      rem--;
      matr[a][b] = matr[b][a] = getDistance(a, b);
    }
    return matr[a][b];
  }
};

int hubDistance(int N, int subtask) {
  int c1 = 0, c2, diam1, diam2;

  vector<int> firstDist(N, 0), secondDist(N, 0), diamdist(N, 0);
  vector<int> distC(N, 0), c1c(N, 0), c2c(N, 0);
  vector<int> fr(1+MAX_DIST, 0);
  QueryStuff api(N);

  c1 = -1, diam1 = -1;
  for(int i = 0; i < N; ++i) {
    if(i != 0)
      firstDist[i] = api.dist(0, i);
    if(firstDist[i] > diam1) {
      diam1 = firstDist[i];
      c1 = i;
    }
  }

  diam2 = c2 = -1;
  for(int i = 0; i < N; ++i) {
    if(i != 0 && i != c1)
      secondDist[i] = api.dist(c1, i);
    if(i == 0)
      secondDist[i] = diam1;
    if(secondDist[i] > diam2) {
      diam2 = secondDist[i];
      c2 = i;
    }

    distC[i] = (firstDist[i] + secondDist[i] - diam1) / 2;
    c1c[i] = firstDist[i] - distC[i];
    c2c[i] = secondDist[i] - distC[i];
    fr[c1c[i]]++;
  }

  int l = 0, r = N;
  for(int i = 0; i <= diam1; ++i) {
    int x;
    x = fr[i];
    r -= x;

    if(fr[i] > N / 2)
      fr[i] = -1;
    else
      fr[i] = max(l, r);

    l += x;
  }

  int rez = 1000000000, centru = 0;

  for(int i = 0; i < N; ++i) {
    int bestdist = max(c2c[i], diam2 - c2c[i]);
    if(bestdist < rez) {
      rez = bestdist;
      centru = c1c[i];
    } else if(bestdist == rez && fr[c1c[i]] < fr[centru])
      centru = c1c[i];
  }

  for(int i = 0; i < N; ++i)
    distC[i] = distC[i] + abs(centru - c1c[i]);

  // Woo wee pot sa fac element majoritar

  vector<int> mlist;
  int bucket = 0, cand;

  for(int i = 0; i < N; ++i) {
    if(mlist.empty())
      mlist.push_back(i);
    else if(api.dist(mlist.back(), i) == distC[mlist.back()] + distC[i]) {
      mlist.push_back(i);
      if(bucket > 0) {
        mlist.push_back(mlist[mlist.size() - 2]);
        --bucket;
      }
    } else
      bucket++;
  }

  cand = mlist.back();
  while(!mlist.empty()) {
    if(api.dist(mlist.back(), cand) < distC[mlist.back()] + distC[cand]) {
      mlist.pop_back();
      if(!mlist.empty())
        mlist.pop_back();
      else
        ++bucket;
    } else {
      mlist.pop_back();
      if(bucket > 0)
        --bucket;
      else
        return rez;
    }
  }

  if(bucket > 0)
    rez = -rez;

  return rez;
}

Compilation message (stderr)

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

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