Submission #167712

#	Time	Username	Problem	Language	Result	Execution time	Memory
167712		faremy	Towns (IOI15_towns)	C++14	100 / 100	21 ms	892 KiB

towns

#include "towns.h"

#include <algorithm>
#include <vector>


struct Leaf
{
	int toLeft, toRight, toDiam, maxDist, index;
	bool operator <(const Leaf &other) const
	{
		return (toLeft < other.toLeft);
	}
};

struct Hub
{
	Hub(int l, int r) : left(l), right(r) {}
	int left, right;
};

const int MAXN = 110;

int distToZero[MAXN];
Leaf towns[MAXN];

std::vector<Hub> hubs;
std::vector<int> candidates;

std::vector<int> equiv[MAXN];
bool seen[MAXN];


bool different(int a, int b)
{
	return (getDistance(towns[a].index, towns[b].index) == towns[a].toDiam + towns[b].toDiam);
}

int floodfill(int node)
{
	if (seen[node])
		return 0;
	seen[node] = true;

	int ans = 1;
	for (int next : equiv[node])
		ans += floodfill(next);
	return ans;
}

int maxsubtree(Hub &hub)
{
	candidates.clear();
	for (int iTown = hub.left; iTown < hub.right; iTown++)
	{
		if (candidates.empty())
			candidates.emplace_back(iTown);
		else if (different(candidates.back(), iTown))
			candidates.pop_back();
		else
		{
			equiv[candidates.back()].emplace_back(iTown);
			equiv[iTown].emplace_back(candidates.back());
			candidates.emplace_back(iTown);
		}
	}

	if (candidates.empty())
		return 0;
	int answer = floodfill(candidates.back());

	for (int iTown = hub.left; iTown < hub.right; iTown++)
		if (!seen[iTown])
			answer += (!different(iTown, candidates.back())) * floodfill(iTown);
	return answer;
}

void reset(int N)
{
	hubs.clear();
	for (int i = 0; i < N; i++)
	{
		equiv[i].clear();
		seen[i] = false;
	}
}

int hubDistance(int N, int sub)
{
	reset(N);

	int furthest = 0, rightEnd = 0;
	for (int iTown = 0; iTown < N; iTown++)
	{
		distToZero[iTown] = getDistance(0, iTown);
		if (distToZero[iTown] > furthest)
		{
			furthest = distToZero[iTown];
			rightEnd = iTown;
		}
	}

	int diameter = 0, leftEnd = 0;
	for (int iTown = 0; iTown < N; iTown++)
	{
		int distToRight = getDistance(iTown, rightEnd);
		if (distToRight > diameter)
		{
			diameter = distToRight;
			leftEnd = iTown;
		}

		towns[iTown].toLeft = (distToZero[rightEnd] + distToZero[iTown] - distToRight) / 2;
		towns[iTown].toRight = distToZero[rightEnd] - towns[iTown].toLeft;
		towns[iTown].toDiam = distToZero[iTown] - towns[iTown].toLeft;
		towns[iTown].index = iTown;
	}

	if (towns[leftEnd].toLeft < towns[leftEnd].toRight)
	{
		for (int iTown = 0; iTown < N; iTown++)
		{
			if (iTown == leftEnd)
				continue;

			if (towns[iTown].toLeft <= towns[leftEnd].toLeft)
			{
				towns[iTown].toDiam += towns[leftEnd].toLeft - towns[iTown].toLeft;
				towns[iTown].toLeft = 0;
				towns[iTown].toRight = towns[leftEnd].toRight;
				towns[iTown].maxDist = towns[iTown].toDiam;
			}
			else
			{
				towns[iTown].toLeft -= towns[leftEnd].toLeft;
				towns[iTown].maxDist = std::max(towns[iTown].toDiam, std::max(towns[iTown].toLeft + towns[leftEnd].toDiam, towns[iTown].toRight));
			}
		}

		towns[leftEnd].toLeft = 0;
		towns[leftEnd].maxDist = std::max(towns[leftEnd].toDiam, towns[leftEnd].toRight);
	}
	else
	{
		for (int iTown = 0; iTown < N; iTown++)
		{
			if (iTown == leftEnd)
				continue;

			if (towns[iTown].toRight <= towns[leftEnd].toRight)
			{
				towns[iTown].toDiam += towns[leftEnd].toRight - towns[iTown].toRight;
				towns[iTown].toLeft = towns[leftEnd].toLeft;
				towns[iTown].toRight = 0;
				towns[iTown].maxDist = towns[iTown].toDiam;
			}
			else
			{
				towns[iTown].toRight -= towns[leftEnd].toRight;
				towns[iTown].maxDist = std::max(towns[iTown].toDiam, std::max(towns[iTown].toLeft, towns[iTown].toRight + towns[leftEnd].toDiam));
			}
		}

		towns[leftEnd].toRight = 0;
		towns[leftEnd].maxDist = std::max(towns[leftEnd].toDiam, towns[leftEnd].toLeft);
	}

	std::sort(towns, towns + N);
	int hubDist = diameter;

	for (int iTown = 0; iTown < N;)
	{
		int jTown = iTown, maxDist = 0;
		while (iTown < N && towns[iTown].toLeft == towns[jTown].toLeft)
		{
			maxDist = std::max(maxDist, towns[iTown].maxDist);
			iTown++;
		}

		if (maxDist < hubDist)
		{
			hubDist = maxDist;
			hubs.clear();
		}

		if (maxDist == hubDist)
		{
			hubs.emplace_back(jTown, iTown);
		}
	}

	bool hasBalanced = false;
	for (Hub &hub : hubs)
		hasBalanced |= (hub.left <= N / 2 && N - hub.right <= N / 2 && maxsubtree(hub) <= N / 2);

	if (hasBalanced)
		return hubDist;
	return -hubDist;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:88:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub)
                            ^~~

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