Submission #95758

#	Time	Username	Problem	Language	Result	Execution time	Memory
95758		tincamatei	Towns (IOI15_towns)	C++14	25 / 100	41 ms	4896 KiB

towns

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

using namespace std;

typedef set<pair<int, int> >::iterator seti;

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

int hubDistance(int N, int subtask) {
  vector<int> diameter(1+MAX_DIST);
  int firstDist[MAX_N], secondDist[MAX_N];

  int c1, c2, diam;
  int rez = MAX_DIST + 1;
  diam = 0;
  c1 = 0;
  for(int i = 1; i < N; ++i) {
    int x = getDistance(0, i);
    if(x > diam) {
      diam = x;
      c1 = i;
    }
  }

  diam = c2 = 0;
  for(int i = 0; i < N; ++i) {
    firstDist[i] = getDistance(c1, i);
    if(firstDist[i] > diam) {
      diam = firstDist[i];
      c2 = i;
    }
  }

  for(int i = 0; i < N; ++i) {
    int c1c, c2c, ic;
    secondDist[i] = getDistance(c2, i);

    ic = (firstDist[i] + secondDist[i] - diam) / 2;
    c1c = firstDist[i] - ic;
    c2c = secondDist[i] - ic;

    diameter[c1c]++;
    rez = min(rez, max(c1c, c2c));
  }

  int leftC = 0, rightC = N;
  for(int i = 0; i <= diam; ++i) {
    rightC -= diameter[i];

    if(min(i, diam - i) == rez && max(max(leftC, rightC), diameter[i]) <= N / 2)
      return rez;

    leftC += diameter[i];
  }
  return -rez;
}

Compilation message (stderr)

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

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