Submission #383821

#	Time	Username	Problem	Language	Result	Execution time	Memory
383821		luciocf	Towns (IOI15_towns)	C++14	48 / 100	22 ms	1004 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 dist[maxn][maxn], nivel[maxn];

bool mark[maxn];

int hubDistance(int N, int subtask)
{
	n = N;
	vector<int> sub, all;
	memset(mark, 0, sizeof mark);

	if (subtask <= 2 || subtask == 4)
	{
		sub.push_back(0); sub.push_back(0); sub.push_back(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 || sobe[i] == diam-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;
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			dist[i][j] = dist[j][i] = getDistance(i, j);

	int mx = 0, u = 1;
	 
	for (int i = 1; i < n; i++)
	{
		if (dist[0][i] > mx)
		{
			mx = dist[0][i];
			u = i;
		}
	}
 
	int v;
	int diam = 0;
 
	for (int i = 0; i < n; i++)
	{
		if (dist[u][i] > diam)
		{
			diam = dist[u][i];
			v = i;
		}
	}
 
	int best = 1e9+10;
 	int from;

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

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

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

			nivel[i] = k;
		}
	}

	sub.push_back(0);
	sub.push_back(0);

	for (int i = 0; i < n; i++)
	{
		if (i == u) sub[0]++;
		else if (i == v) sub[1]++;
		else if (sobe[i] == best || sobe[i] == diam-best) all.push_back(i);
		else if (qual[i] == u) sub[0]++;
		else sub[1]++;
	}

	for (auto i: all)
	{
		if (mark[i]) continue;

		mark[i] = 1;
		sub.push_back(1);

		for (auto j: all)
			if (!mark[j] && dist[i][j] < nivel[i]+nivel[j])
				mark[j] = 1, sub.back()++;
	}

	if (*max_element(sub.begin(), sub.end()) <= n/2) return best;

	all.clear();
	sub.clear();
	memset(mark, 0, sizeof mark);

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

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

			if (dist[u][i]-nivel[i] < best) second = max(second, dist[u][i]-nivel[i]);
		}

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

		for (int i = 0; i < n; i++)
			if (i == u || dist[u][i]-nivel[i] == second)
				all.push_back(i);

		int soma = 0;

		for (auto i: all)
		{
			if (mark[i]) continue;

			mark[i] = 1;
			sub.push_back(1);

			for (auto j: all)
				if (!mark[j] && dist[i][j] < nivel[i]+nivel[j])
					mark[j] = 1, sub.back()++;

			soma += sub.back();
		}

		if (max(*max_element(sub.begin(), sub.end()), n-soma) <= n/2) return best;
		return -best;
	}
	else
	{
		int second = 0;

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

			if (dist[v][i]-nivel[i] < best) second = max(second, dist[v][i]-nivel[i]);
		}

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

		for (int i = 0; i < n; i++)
			if (i == v || dist[v][i]-nivel[i] == second)
				all.push_back(i);

		int soma = 0;

		for (auto i: all)
		{
			if (mark[i]) continue;

			mark[i] = 1;
			sub.push_back(1);

			for (auto j: all)
				if (!mark[j] && dist[i][j] < nivel[i]+nivel[j])
					mark[j] = 1, sub.back()++;

			soma += sub.back();
		}

		if (max(*max_element(sub.begin(), sub.end()), n-soma) <= n/2) return best;
		return -best;
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:93:21: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     if (i == u || i == v) continue;
      |                   ~~^~~~
towns.cpp:277:27: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  277 |    if (i == v || dist[v][i]-nivel[i] == second)
      |                  ~~~~~~~~~^
towns.cpp:227:2: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
  227 |  if (from == u)
      |  ^~
towns.cpp:87:3: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |   if (from == u)
      |   ^~

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