Submission #617011

#	Time	Username	Problem	Language	Result	Execution time	Memory
617011		Lucpp	Towns (IOI15_towns)	C++17	100 / 100	19 ms	852 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())

int hubDistance(int n, int sub) {
	sub--; // suppress unused warning
	vector<int> d0(n), du(n);
	for(int i = 1; i < n; i++) d0[i] = getDistance(0, i);
	int u = int(max_element(d0.begin(), d0.end())-d0.begin());
	for(int i = 0; i < n; i++) if(u!=i) du[i] = getDistance(u, i);
	int v = int(max_element(du.begin(), du.end())-du.begin());
	int l = 0, r = 0;
	vector<int> xl, xr;
	int maxB = 0, maxC = 0;
	for(int i = 0; i < n; i++){
		int b = (d0[u]+d0[i]-du[i])/2;
		int c = d0[u]-b;
		if(b+du[v]-d0[u] <= du[v]/2){
			if(b < maxB) l++;
			if(b > maxB) l+=sz(xl), xl.clear(), maxB = b;
			if(b == maxB) xl.push_back(i);
		}
		if(c <= du[v]/2){
			if(c < maxC) r++;
			if(c > maxC) r+=sz(xr), xr.clear(), maxC = c;
			if(c == maxC) xr.push_back(i);
		}
	}
	int R = min(d0[u]-maxB, du[v]-maxC);
	vector<int> x;
	bool ok = false;
	// cerr << maxB << " " << maxC << " " << l << " " << r << " " << sz(xl) << " " << sz(xr) << "\n";
	if(d0[u]-maxB == R){
		if(l <= n/2 && r+sz(xr) <= n/2) x = xl, ok = true;
	}
	if(du[v]-maxC == R){
		if(l+sz(xl) <= n/2 && r <= n/2) x = xr, ok = true;
	}
	if(xl == xr){
		if(l <= n/2 && r <= n/2) x = xl, ok = true;
	}
	if(!ok) return -R;
	auto same = [&](int a, int b){
		return getDistance(a, b) < (d0[a]+du[a]-d0[u])/2 + (d0[b]+du[b]-d0[u])/2;
	};
	vector<int> cache(sz(x), -1);
	int cnt = 1;
	int cur = 0;
	cache[0] = 0;
	for(int i = 1; i < sz(x); i++){
		if(same(x[cur], x[i])) cnt++, cache[i] = cur;
		else if(--cnt == 0){
			cur = i;
			cnt = 1;
			cache[i] = cur;
		}
	}
	int other = 0;
	bool isSame = false;
	for(int i = 0; i < sz(x); i++){
		// cerr << cache[i] << "\n";
		if(other >= (n+1)/2) break;
		if(cache[i] == i){
			if(isSame) isSame = false;
			else isSame = same(x[cur], x[i]);
		}
		if(cache[i] != -1 && !isSame) other++;
		if(cache[i] == -1 && isSame) other++;
		if(cache[i] == -1 && !isSame) other += !same(x[cur], x[i]);
	}
	if(sz(x)-other <= n/2) return R;
	else return -R;
}

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