Submission #1122118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122118		epicci23	Towns (IOI15_towns)	C++17	25 / 100	13 ms	1104 KiB

towns

#include "bits/stdc++.h"
#include "towns.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

array<int,3> solve(int ab,int ac,int bc){
  int abc = (ab+ac+bc)/2;
  int a = abc - bc;
  int b = abc - ac;
  int c = abc - ab;
  return {a,b,c};
}

int hubDistance(int N, int sub){
  int dia1 = 0 , cur = 0;
  for(int i = 0; i < N ;i++){
  	int u = getDistance(0, i);
  	if(u > cur){
  	 dia1 = i;
  	 cur = u; 
  	}
  }

  int dia2 = dia1; cur = 0;
  
  vector<int> uz1(N,0),uz2(N,0);

  for(int i = 0; i < N ; i++){
  	int u = getDistance(dia1, i);
  	uz1[i] = u;
  	if(u > cur){
  	 dia2 = i;
  	 cur = u; 
  	}
  }
  
  int res = (int)2e9+5;

  for(int i = 0; i < N; i++) uz2[i] = getDistance(dia2,i);
  for(int i = 0; i < N; i++){
    auto x = solve(cur,uz1[i],uz2[i]);
    if(max({x[0],x[1],x[2]}) < res) res = max({x[0],x[1],x[2]});
  }

  return res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:15:28: warning: unused parameter 'sub' [-Wunused-parameter]
   15 | 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