Submission #383731

#	Time	Username	Problem	Language	Result	Execution time	Memory
383731		luciocf	Towns (IOI15_towns)	C++14	25 / 100	24 ms	492 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
 
using namespace std;
 
const int maxn = 120;
 
int n;
 
int du[maxn];
 
int hubDistance(int N, int sub)
{
	n = N;
 
	int mx = 0, u = 1;
 
	for (int i = 1; i < n; i++)
	{
		int x = getDistance(0, i);
 
		if (x > mx)
		{
			mx = x;
			u = i;
		}
	}
 
	int v;
	int diam = 0;
 
	for (int i = 0; i < n; i++)
	{
		du[i] = getDistance(u, i);
 
		if (du[i] > diam)
		{
			diam = du[i];
			v = i;
		}
	}
 
	int best = 1e9+10;
 
	for (int i = 0; i < n; i++)
	{
		if (i != u && i != v)
		{
			int dv = getDistance(v, i);
 
			int k = (du[i] + dv - diam)/2;
 
			best = min(best, max(du[i]-k, dv-k));
		}
	}
 
	return -best;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:12:28: warning: unused parameter 'sub' [-Wunused-parameter]
   12 | int hubDistance(int N, int sub)
      |                        ~~~~^~~
towns.cpp:49:24: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |    int dv = getDistance(v, i);
      |             ~~~~~~~~~~~^~~~~~

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