Submission #556766

#	Time	Username	Problem	Language	Result	Execution time	Memory
556766		blue	Towns (IOI15_towns)	C++17	25 / 100	16 ms	956 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);
	for(int i = 0; i < N; i++)
		dist0[i] = getDistance(0, i);

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

	vi distS(N);

	int T = 0;
	for(int i = 0; i < N; i++)
	{
		distS[i] = getDistance(S, i);
		if(distS[i] > distS[T])
			T = i;
	}

	vi distT(N);
	for(int i = 0; i < N; i++)
		distT[i] = getDistance(T, i);

	int ST = distS[T];

	int res = 5'000'000;

	for(int i = 0; i < N; i++)
		res = min(res, max(distS[i], distT[i]) - (distS[i] + distT[i] - distS[T])/2);

	return res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:39:6: warning: unused variable 'ST' [-Wunused-variable]
   39 |  int ST = distS[T];
      |      ^~
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