Submission #1217196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217196		Lemser	Towns (IOI15_towns)	C++20	In queue	0 ms	0 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

/*
getDistance (i, j)
*/
const int INF = 1e18;

vector<int> d_0, d_a, d_x;

bool same (ll i, ll j) {
	return (getDistance(i, j) < d_a[i] + d_a[j] - 2ll*d_x[i]);
}

vector<int> unite (vector<int> a, vector<int> b) {
	vector<int> c;
	for (ll i: a) c.pb(i);
	for (ll i: b) c.pb(i);
	return c;
}

// si hay un elemento mayoritario este retornara su frecuencia
int solve (vector<int> vec) {
	vector<vector<int>> alive, dead;
	fo (i, vec.size()) alive.pb({i});
	while (alive.size() > 1) {
		vector<vector<int>> nalive;
		for (ll i = 0; i+1 < alive.size(); i += 2) {
			auto a = alive[i], b = alive[i+1];
			if (same(vec[a[0]], vec[b[0]])) {
				nalive.pb(unite(a, b));
			} else {
				dead.pb(a);
				dead.pb(b);
			}
		}
		if (alive.size()&1) {
            if (nalive.size() > 0)
			    dead.pb(alive.back());
            else nalive.pb(alive.back());
		}
		alive = nalive;
	}
    if (alive.size() == 0) return 0;
	for (vector<int> g: dead) {
		if (same(vec[alive[0][0]], vec[g[0]])) {
            for (ll i: g) alive[0].pb(i);
		}
	}
	return alive[0].size();
}

int hubDistance(int N, int sub) {
	int a, b;
	d_0 = vector<int>(N, 0);
	d_a = vector<int>(N, 0);
	d_x = vector<int>(N, 0);
	for (int i = 1; i < N; i++) d_0[i] = getDistance(0, i);
	for (int i = 0; i < N; i++) if (d_0[i] == *max_element(all(d_0))) {
		a = i;
		break;
	}
	d_a[0] = d_0[a];
	for (int i = 1; i < N; i++) {
		if (i == a) continue;
		d_a[i] = getDistance (a, i);
	}
	for (int i = 0; i < N; i++) if (d_a[i] == *max_element(all(d_a))) {
		b = i;
		break;
	}
	int R = INF, mid = (d_a[0] + d_a[b] - d_0[b])/2;
	map<int, vector<int>> mp;
	for (int i = 0; i < N; i++) {
		d_x[i] = (d_a[i] + d_a[0] - d_0[i])/2;
		if (d_x[i] > mid || i == a || i == b) continue;
		mp[d_x[i]].pb(i);
		R = min(R, max(d_x[i], d_a[b]-d_x[i]));
	}
	ll sum = 1;
	for (auto [k, vec]: mp) {
		ll t = vec.size();
		if (sum > N/2) break;
		if (N - sum - t > N/2 || max(k, d_a[b] - k) > R) {
			sum += t;
			continue;
		}
		if (t <= N/2) return R;
		if (solve(vec) > N/2) return -R;
		return R;
	}
	return -R;
}