Submission #1109714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109714		jerzyk	Towns (IOI15_towns)	C++17	100 / 100	21 ms	1008 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int AN = 1007;
int vis[AN];
int dis[2][AN];
int centd;

void Clean(int n)
{
	centd = 0;
	for(int r = 0; r < 2; ++r)
		for(int i = 0; i < n + 3; ++i)
			dis[r][i] = 0;
	for(int i = 0; i < n; ++i)
		vis[i] = 0;
}

void Do(int n, int &a, int &b)
{
	pair<int, int> ma = make_pair(-1, -1);
	for(int i = 1; i < n; ++i)
	{
		dis[0][i] = getDistance(0, i);
		ma = max(ma, make_pair(dis[0][i], -i));
	}
	a = -ma.nd;
	dis[1][0] = ma.st;
	ma = make_pair(dis[1][0], 0);
	for(int i = 1; i < n; ++i)
	{
		if(i == a) continue;
		dis[1][i] = getDistance(a, i);
		ma = max(ma, make_pair(dis[1][i], -i));
	}
	b = -ma.nd;
}

void Fix(vector<int> &a)
{
	vector<int> nw;
	sort(a.begin(), a.end());
	for(int i = 0; i < (int)a.size(); ++i)
		if(i == 0 || a[i] != a[i - 1])
			nw.pb(a[i]);
	a = nw;
}

int D(int x)
{
	return (dis[1][0] + dis[1][x] - dis[0][x]) / 2;
}

int Dc(int x)
{
	int ans = dis[1][x] - D(x);
	int dod = D(x) - centd;
	if(dod < 0) dod *= -1;
	return ans + dod;
}

bool Cp(int a, int b)
{
	return (getDistance(a, b) != Dc(a) + Dc(b));
}

bool Check(int n)
{
	//cerr << "\n\n";
	int cur = 0;
	vector<int> v;
	for(int i = 0; i < n; ++i)
	{
		if(v.size() == 0)
		{
			v.pb(i);
			++cur; vis[i] = cur;
			continue;
		}
		if(Cp(v[0], i))
		{
			v.pb(i);
			vis[i] = cur;
		}else
		{
			v.pop_back();
		}
	}
	//for(int i = 0; i < n; ++i)
		//cerr << "V: " << i << " " << vis[i] << " " << Dc(i) << "\n";
	if(v.size() == 0) return true;
	int il = 0, u = v[0];
	for(int i = 0; i < n; ++i)
	{
		if(vis[i] == -1) continue;
		if(vis[i] == vis[u])
		{++il; continue;}
		if(vis[i] == 0)
		{
			if(Cp(u, i)) ++il;
			continue;
		}
		bool czy = Cp(u, i);
		if(czy) ++il;
		for(int j = i + 1; j < n; ++j)
			if(vis[j] == vis[i])
			{
				vis[j] = -1;
				if(czy) ++il;
			}
	}
	if(il <= (n / 2)) return true;
	return false;
}

int hubDistance(int _NN, int _sub)
{
	//cerr << "\n";
	Clean(_NN);
	int n = _sub;
	n = _NN;
	int a, b;
	Do(n, a, b);
	vector<int> pth;
	int xd = D(b);
	for(int i = 0; i < n; ++i)
	{
		int cur = D(i);
		if(cur <= xd)
			pth.pb(cur);
		//cerr << i << " " << D(i) << "\n";
	}
	//cerr << a << " " << b << " xd " << xd << "\n";
	Fix(pth);
	int ans = II; int pos = -1;
	for(int i = 0; i < (int)pth.size(); ++i)
	{
		if(max(pth[i], dis[1][b] - pth[i]) < ans)
			pos = i;
		ans = min(ans, max(pth[i], dis[1][b] - pth[i]));
	}
	int il = 0;
	for(int i = 0; i < n; ++i)
		if(D(i) <= pth[pos])
			++il;

	if(il <= (n / 2) && pos < (int)pth.size() - 1 && ans == max(pth[pos + 1], dis[1][b] - pth[pos + 1])) ++pos;
	centd = pth[pos];
	//cerr << centd << "\n";

	bool m = Check(n);
	if(!m) ans *= -1;

	return ans;
}

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