Submission #683075

#	Time	Username	Problem	Language	Result	Execution time	Memory
683075		MilosMilutinovic	도시들 (IOI15_towns)	C++14	0 / 100	2 ms	568 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));
  for (int i = 0; i < n; i++) {
    w[i][i] = 0;
  }
  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<int> f;
  vector<int> d(n);
  for (int i = 0; i < n; i++) {
    if (u == i || v == i) {
      continue;
    }
    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;
    d[i] = d_vi - dv;
    res = min(res, max(dv, du));
    f.push_back(dv);
  }
  vector<int> sz(n, 1);
  vector<int> par(n);
  iota(par.begin(), par.end(), 0);
  function<int(int)> GetRoot = [&](int x) {
    return par[x] == x ? x : par[x] = GetRoot(par[x]);
  };
  auto Merge = [&](int x, int y) {
    x = GetRoot(x);
    y = GetRoot(y);
    if (x != y) {
      sz[x] += sz[y];
      par[y] = x;
    }
  };
  vector<int> ch;
  for (int i = 0; i < (int) f.size(); i++) {
    if (i == 0 || f[i] != f[i - 1]) {
      ch.push_back(1);
    } else {
      ch.back() += 1;
    }
  }
  sort(f.begin(), f.end());
  f.erase(unique(f.begin(), f.end()));
  int m = (int) f.size();
  {
    int L = 1, R = n - 1;
    for (int i = 0; i < m; i++) {
      R -= ch[i];
      if (res == max(f[i], diam - f[i])) {
        if (L <= n / 2 && R <= n / 2 && ch[i] <= n / 2) {
          return res;
        }
      }
      L += ch[i];
    }
  }
  auto Connected = [&](int x, int y) {
    int d_xy = Ask(x, y);
    return d_xy < d[x] + d[y];
  };
  auto Solve = [&](int r) {
    vector<int> ver;
    for (int i = 0; i < n; i++) {
      if (i != u && i != v && -d[i] + Ask(v, i) == f[r]) {
        ver.push_back(i);
      }
    }
    vector<vector<int>> cc;
    for (int x : ver) {
      cc.push_back(vector<int>(1, x));
    }
    while (cc.size() > 1) {
      if ((int) cc.size() % 2 == 1) {
        cc.pop_back();
      }
      vector<vector<int>> new_cc;
      for (int i = 0; i < (int) cc.size(); i += 1) {
        if (Connected(cc[i][0], cc[i + 1][0])) {
          vector<int> tmp;
          for (int x : cc[i]) {
            tmp.push_back(x);
          }
          for (int x : cc[i + 1]) {
            tmp.push_back(x);
          }
          new_cc.push_back(tmp);
        }
      }
      swap(cc, new_cc);
    }
    if (cc.empty()) {
      return true;
    }
    vector<bool> in(n);
    for (int p : cc[0]) {
      in[p] = true;
    }
    for (int i = 0; i < n; i++) {
      if (!in[i] && Connected(i, cc[0][0])) {
        in[i] = true;
      }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        cnt += 1;
      }
    }
    return cnt <= n / 2;
  };
  int L = 1, R = n - 1;
  for (int i = 0; i < m; i++) {
    R -= ch[i];
    if (res == max(f[i], diam - f[i])) {
      if (L <= n / 2 && R <= n / 2 && Solve(i)) {
        return res;
      }
    }
    L += ch[i];
  }
  return -res;
}

/*
1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0

17
*/

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:23:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   23 |     v = max_element(dist.begin(), dist.end()) - dist.begin();
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:30:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   30 |     u = max_element(dist.begin(), dist.end()) - dist.begin();
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:57:8: warning: variable 'Merge' set but not used [-Wunused-but-set-variable]
   57 |   auto Merge = [&](int x, int y) {
      |        ^~~~~
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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