Submission #383754

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

towns

#include <bits/stdc++.h>
#include "towns.h"
 
using namespace std;
 
const int maxn = 120;
 
int n;
 
int du[maxn], dv[maxn];

int sobe[maxn], qual[maxn];

int sub[3];
 
int hubDistance(int N, int subtask)
{
	n = N;
	sub[0] = sub[1] = sub[2] = 0;
 
	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;
 	int from;

	for (int i = 0; i < n; i++)
	{
		if (i != u && i != v)
		{
			dv[i] = getDistance(v, i);
 
			int k = (du[i] + dv[i] - diam)/2;
 
			best = min(best, max(du[i]-k, dv[i]-k));

			if (best == du[i]-k) from = u;
			else if (best == dv[i]-k) from = v;

			if (du[i]-k <= dv[i]-k) sobe[i] = du[i]-k, qual[i] = u;
			else sobe[i] = dv[i]-k, qual[i] = v;
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (i == u) sub[0]++;
		else if (i == v) sub[2]++;
		else if (sobe[i] == best) sub[1]++;
		else if (qual[i] == u) sub[0]++;
		else sub[2]++;
	}

	if (max({sub[0], sub[1], sub[2]}) <= n/2) return best;

	if (from == u)
	{
		int second = 0;

		for (int i = 0; i < n; i++)
		{
			if (i == u || i == v) continue;

			int k = (du[i] + dv[i] - diam)/2;

			if (du[i]-k < best) second = max(second, du[i]-k);
		}

		if (second != diam-best) return -best;

		sub[1] += sub[2];
		sub[2] = 0;

		for (int i = 0; i < n; i++)
		{
			if (i == u || i == v) continue;

			int k = (du[i] + dv[i] - diam)/2;

			if (du[i]-k == second) sub[2]++;
		}

		if (max({n-sub[1]-sub[2], sub[1], sub[2]}) <= n/2) return best;
		return -best;
	}
	else
	{
		int second = 0;

		for (int i = 0; i < n; i++)
		{
			if (i == u || i == v) continue;

			int k = (du[i] + dv[i] - diam)/2;

			if (dv[i]-k < best) second = max(second, dv[i]-k);
		}

		if (second != diam-best) return -best;

		sub[1] += sub[0];
		sub[2] = 0;

		for (int i = 0; i < n; i++)
		{
			if (i == u || i == v) continue;

			int k = (du[i] + dv[i] - diam)/2;

			if (dv[i]-k == second) sub[2]++;
		}

		if (max({n-sub[1]-sub[2], sub[1], sub[2]}) <= n/2) return best;
		return -best;
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:16:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   16 | int hubDistance(int N, int subtask)
      |                        ~~~~^~~~~~~
towns.cpp:86:20: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |    if (i == u || i == v) continue;
      |                  ~~^~~~
towns.cpp:80:2: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |  if (from == u)
      |  ^~

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