Submission #556772

#	Time	Username	Problem	Language	Result	Execution time	Memory
556772		blue	Towns (IOI15_towns)	C++17	25 / 100	13 ms	356 KiB

towns

#include "towns.h"
#include <vector>
#include <cmath>
#include <set>
#include <iostream>
using namespace std;

namespace
{
	using vi = vector<int>;
}


int hubDistance(int N, int sub) 
{
	vi dist0(N);
	dist0[0] = 0;
	for(int i = 1; i < N; i++)
		dist0[i] = getDistance(0, i);

	int S = 0;
	for(int i = 1; i < N; i++)
		if(dist0[i] > dist0[S])
			S = i;

	int ST = 0; //diameter

	// cerr << "done\n";

	vi distS(N);
	distS[S] = 0;
	distS[0] = dist0[S];

	int T = 0;
	ST = distS[0];

	for(int i = 1; i < N; i++)
	{
		if(i != S)
		{
			distS[i] = getDistance(S, i);

			if(distS[i] > ST)
			{
				ST = distS[i];
				T = i;
			}
		}
	}

	// cerr << "S = " << S << "\n";


	vi S0_dist(N);
	for(int i = 0; i < N; i++)
		S0_dist[i] = (distS[i] + dist0[i] - distS[0])/2;

	vi xcoord(N);
	for(int i = 0; i < N; i++)
		xcoord[i] = distS[i] - S0_dist[i];

	int res = 5'000'000;

	for(int i = 0; i < N; i++)
		res = min(res, max(xcoord[i], ST - xcoord[i]));

	return res;

	// int best_diff = 5'000'000;
	// set<int> best_coords;
	// for(int i = 0; i < N; i++)
	// {
	// 	// int ist = 

	// 	if(abs(2*xcoord[i] - ST) < best_diff)
	// 	{
	// 		best_coords.clear();
	// 		best_diff = abs(2*xcoord[i] - ST);
	// 	}
		
	// 	if(abs(2*xcoord[i] - ST) == best_diff)
	// 		best_coords.insert(xcoord[i]);
	// }

	// // cerr << "best coords = ";
	// // for(int b : best_coords) cerr << b << ' ';
	// // 	cerr << '\n';

	// // cerr << "returning: \n";

	// return *best_coords.rbegin();
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:34:6: warning: variable 'T' set but not used [-Wunused-but-set-variable]
   34 |  int T = 0;
      |      ^
towns.cpp:14:28: warning: unused parameter 'sub' [-Wunused-parameter]
   14 | 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