Submission #682726

#	Time	Username	Problem	Language	Result	Execution time	Memory
682726		MilosMilutinovic	Towns (IOI15_towns)	C++14	25 / 100	14 ms	860 KiB

towns

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

using namespace std;

int hubDistance(int n, int sub) {
  vector<vector<int>> w(n, vector<int>(n, -1));
  auto Ask = [&](int i, int j) {
    if (w[i][j] == -1) {
      w[i][j] = w[j][i] = getDistance(i, j);
    }
    return w[i][j];
  };
  int v, u;
  {
    vector<int> dist(n);
    for (int i = 1; i < n; i++) {
      dist[i] = Ask(0, i);
    }
    v = max_element(dist.begin(), dist.end()) - dist.begin();
  }
  {
    vector<int> dist(n);
    for (int i = 0; i < n; i++) {
      dist[i] = Ask(i, v);
    }
    u = max_element(dist.begin(), dist.end()) - dist.begin();
  }
  int diam = Ask(v, u);
  int res = diam;
  vector<pair<int, int>> f;
  for (int i = 0; i < n; i++) {
    int d_vi = Ask(v, i);
    int d_ui = Ask(u, i);
    int diff = d_vi - d_ui;
    // dv + du = diam
    // dv - du = diff
    int dv = (diam + diff) / 2;
    int du = diam - dv;
    res = min(res, max(dv, du));
    f.emplace_back(dv, 1);
  }
  vector<pair<int, int>> new_f;
  for (auto& p : f) {
    if (new_f.empty() || new_f.back().first != p.first) {
      new_f.push_back(p);
    } else {
      new_f.back().second += 1;
    }
  }
  swap(f, new_f);
  int L = 1, R = n - 1;
  for (auto& p : f) {
    R -= p.second;
    if (L <= n / 2 && R <= n / 2 && p.first <= n / 2) {
      return res;
    }
    L += p.second;
  }
  return -res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:20:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   20 |     v = max_element(dist.begin(), dist.end()) - dist.begin();
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:27:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   27 |     u = max_element(dist.begin(), dist.end()) - dist.begin();
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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