Submission #387343

#	Time	Username	Problem	Language	Result	Execution time	Memory
387343		Keshi	Towns (IOI15_towns)	C++17	48 / 100	23 ms	1004 KiB

towns

//In the name of God
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 200;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

int d[3][maxn], dis[maxn], sz[maxn], h[maxn];
int dist[maxn][maxn];
pll p[maxn];
vector<ll> vec[maxn];

int solve3(int n){
	for(ll i = 0; i < n; i++){
		for(ll j = i + 1; j < n; j++){
			dist[i][j] = dist[j][i] = getDistance(i, j);
		}
	}
	ll v = 0;
	for(ll i = 1; i < n; i++){
		d[0][i] = dist[0][i];
		if(d[0][i] > d[0][v]) v = i;
	}
	ll u = 0;
	for(ll i = 0; i < n; i++){
		d[1][i] = dist[v][i];
		if(d[1][i] > d[1][u]) u = i;
	}
	for(ll i = 0; i < n; i++){
		d[2][i] = dist[u][i];
	}
	ll D = d[1][u];
	map<ll, ll> mp;
	ll t = 1;
	for(ll i = 0; i < n; i++){
		h[i] = (d[1][i] + d[2][i] - D) / 2;
		if(!mp[d[1][i] - h[i]]){
			mp[d[1][i] - h[i]] = t;
			dis[t] = d[1][i] - h[i];
			vec[t].clear();
			t++;
		}
		vec[mp[d[1][i] - h[i]]].pb(i);
	}
	ll R = inf;
	for(ll i = 1; i < t; i++){
		R = min(R, max(dis[i], D - dis[i]));
		sz[i] = Sz(vec[i]);
		p[i] = Mp(dis[i], i);
	}
	sort(p + 1, p + t);
	bool f = 0;
	ll ssz = 0;
	for(ll i = 1; i < t; i++){
		ll j = p[i].S;
		if(R == max(p[i].F, D - p[i].F)){
			if(ssz > n / 2 || (n - sz[j] - ssz > n / 2)) continue;
			bool ff = 1;
			for(ll v1 : vec[j]){
				ll e = 0;
				for(ll v2 : vec[j]){
					if(dist[v1][v2] != h[v1] + h[v2]) e++;
				}
				if(e > n / 2) ff = 0;
			}
			if(ff) f = 1;
		}
		ssz += sz[j];
	}
	if(!f) R *= -1;
	return R;
}

int solve4(int n){
	ll v = 0;
	for(ll i = 1; i < n; i++){
		d[0][i] = getDistance(0, i);
		if(d[0][i] > d[0][v]) v = i;
	}
	ll u = 0;
	for(ll i = 0; i < n; i++){
		d[1][i] = getDistance(v, i);
		if(d[1][i] > d[1][u]) u = i;
	}
	for(ll i = 0; i < n; i++){
		d[2][i] = getDistance(u, i);
	}
	ll D = d[1][u];
	map<ll, ll> mp;
	ll t = 1;
	for(ll i = 0; i < n; i++){
		h[i] = (d[1][i] + d[2][i] - D) / 2;
		if(!mp[d[1][i] - h[i]]){
			mp[d[1][i] - h[i]] = t;
			dis[t] = d[1][i] - h[i];
			sz[t] = 0;
			t++;
		}
		sz[mp[d[1][i] - h[i]]]++;
	}
	ll R = inf;
	for(ll i = 1; i < t; i++){
		R = min(R, max(dis[i], D - dis[i]));
		p[i] = Mp(dis[i], sz[i]);
	}
	sort(p + 1, p + t);
	bool f = 0;
	ll ssz = 0;
	for(ll i = 1; i < t; i++){
		if(R == max(p[i].F, D - p[i].F)){
			if(p[i].S <= n / 2 && ssz <= n / 2 && (n - p[i].S - ssz) <= n / 2) f = 1;
		}
		ssz += p[i].S;
	}
	if(!f) R *= -1;
	return R;
}

int hubDistance(int n, int sub){
	if(sub == 3) return solve3(n);
	return solve4(n);
}

/*int main(){
    fast_io;



    return 0;
}*/

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