Submission #384191

#	Time	Username	Problem	Language	Result	Execution time	Memory
384191		luciocf	Towns (IOI15_towns)	C++14	25 / 100	22 ms	384 KiB

towns

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

vector<int> all;

bool check(int u, int v)
{
	int n_u = (qual[u] ? du[u] - sobe[u] : d0[u] - sobe[u]);
	int n_v = (qual[v] ? du[v] - sobe[v] : d0[v] - sobe[v]);

	return getDistance(u, v) < n_u + n_v;
}

int get_major(void)
{
	vector<int> lista, bucket;

	for (auto w: all)
	{
		if (!lista.size())
		{
			lista.push_back(w);
			continue;
		}

		if (check(w, lista.back())) bucket.push_back(w);
		else
		{
			lista.push_back(w);

			if (bucket.size())
			{
				lista.push_back(bucket.back());
				bucket.pop_back();
			}
		}
	}

	int T = lista.back();
	int cnt = 0;

	while (lista.size())
	{
		if (check(T, lista.back()))
		{
			cnt++;
			lista.pop_back();
			if (lista.size()) lista.pop_back();
		}
		else
		{
			lista.pop_back();

			if (!bucket.size())
			{
				cnt = 0;
				break;
			}

			cnt++;
			bucket.pop_back();
		}
	}

	return cnt;
}
 
int hubDistance(int N, int subtask)
{
	n = N;
	all.clear();
 
	int mx = 0, u = 1;
 
	for (int i = 1; i < n; i++)
	{
		d0[i] = getDistance(0, i);
 
		if (d0[i] > mx)
		{
			mx = d0[i];
			u = i;
		}
	}
 	
 	int diam = 0, v = 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 = 1; i < n; i++)
	{
		if (i != u)
		{
			int k = (du[i] + d0[i] - mx)/2;
 			
			best = min(best, max(du[i]-k, diam-(du[i]-k)));

			if (best == du[i]-k) from = u;
			else if (best == diam-(du[i]-k)) from = 0;

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

	int A = 0, B = 0;

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

	if (max({A, B, get_major()}) <= n/2) return best;
 
	all.clear();
	A = B = 0;
 
	if (from == u)
	{
		int second = 0;

		for (int i = 1; i < n; i++)
		{
			if (i == u) continue;
 
			if (qual[i] == u && sobe[i] < best) second = max(second, sobe[i]);
		}
 
		if (second != diam-best) return -best;
 
		for (int i = 0; i < n; i++)
		{
			if (i == u) A++;
			else if (i == 0) B++;
			else if (qual[i] == u && sobe[i] == second) all.push_back(i);
			else if (qual[i] == u) A++;
			else B++;
		}

		if (max({A, B, get_major()}) <= n/2) return best;
	}
	else
	{
		int second = 0;

		for (int i = 1; i < n; i++)
			if (qual[i] == 0 && sobe[i] < best)
				second = max(second, sobe[i]);
 
		if (second != diam-best) return -best;
 
		for (int i = 0; i < n; i++)
		{
			if (i == u) A++;
			else if (i == 0) B++;
			else if (qual[i] == 0 && sobe[i] == second) all.push_back(i);
			else if (qual[i] == u) A++;
			else B++;
		}

		if (max({A, B, get_major()}) <= n/2) return best;
	}

	return -best;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:96:17: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   96 |   int diam = 0, v = 0;
      |                 ^
towns.cpp:78:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   78 | int hubDistance(int N, int subtask)
      |                        ~~~~^~~~~~~
towns.cpp:144:2: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |  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