Submission #1109690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109690		jerzyk	Towns (IOI15_towns)	C++17	25 / 100	17 ms	1016 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 dis[2][AN];

void Clean(int n)
{
	for(int r = 0; r < 2; ++r)
		for(int i = 0; i < n + 3; ++i)
			dis[r][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 hubDistance(int _NN, int _sub)
{
	//cerr << "XD\n";
	Clean(_NN);
	int n = _sub;
	n = _NN;
	int a, b;
	Do(n, a, b);
	vector<int> pth;
	int xd = (dis[1][0] + dis[1][b] - dis[0][b]) / 2;
	for(int i = 0; i < n; ++i)
	{
		int cur = (dis[1][0] + dis[1][i] - dis[0][i]) / 2;
		if(cur <= xd)
			pth.pb(cur);
	}
	//cerr << a << " " << b << " xd " << xd << "\n";
	Fix(pth);
	int ans = II;
	for(int i = 0; i < (int)pth.size(); ++i)
		ans = min(ans, max(pth[i], dis[1][b] - pth[i]));
	//cerr << ans << "\n";
	return ans;
}

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