제출 #1306294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306294		rolandpetrean	도시들 (IOI15_towns)	C++20	25 / 100	10 ms	1852 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
// #define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
using ti = array<int, 3>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int hubDistance(int n, int sub) {
  pi maxi{-1, -1};
	for (int i = 1; i < n; ++i) {
    maxi = max(maxi, pi{getDistance(0, i), i});
  }
  
  int u = maxi[1];
  maxi = {-1, -1};
  vector<int> dist_u(n), dist_v(n);
  for (int i = 0; i < n; ++i) {
    dist_u[i] = getDistance(u, i);
    maxi = max(maxi, pi{dist_u[i], i});
  }
  int v = maxi[1];
  for (int i = 0; i < n; ++i) {
    dist_v[i] = getDistance(v, i);
  }
  
  int d = dist_u[v], R = 1e9;
  for (int i = 0; i < n; ++i) {
    int here = dist_u[i] + dist_v[i];
    here -= d;
    here /= 2;
    here = max(dist_u[i] - here, dist_v[i] - here);
    R = min(R, here);
  }
  
  return R;
}


/*

*/

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