Submission #52096

#	Time	Username	Problem	Language	Result	Execution time	Memory
52096		kingpig9	Towns (IOI15_towns)	C++11	100 / 100	28 ms	724 KiB

towns

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 115;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

int N;
int dist[MAXN][MAXN];

int getdist (int x, int y) {
	assert(0 <= x && x < N);
	assert(0 <= y && y < N);
	if (x == y) {
		return 0;
	}
	if (x > y) {
		swap(x, y);
	}
	if (dist[x][y] == 0) {
		dist[x][y] = getDistance(x, y);
	}
	return dist[x][y];
}

int getcent (int a, int b, int c) {
	//distance from a to center(a, b, c)
	return (getdist(a, b) + getdist(a, c) - getdist(b, c)) / 2;
}

int diamx, diamy, diam;
int dxcent;
int ans;
int distl[MAXN];	//distance to left of diameter
map<int, int> mp, psum;	//map of branches sizes, prefix sums

void reset() {
	fillchar(dist, 0);
	diamx = diamy = diam = ans = 0;
	for (int i = 0; i < MAXN; i++) {
		distl[i] = 0;
	}
	mp.clear();
	psum.clear();
}

pii getfar (int x) {
	pii f(0, x);
	for (int i = 0; i < N; i++) {
		setmax(f, pii(getdist(i, x), i));
	}
	return f;
}

void calc_diam() {
	pii far0 = getfar(0);
	diamx = far0.se;
	tie(diam, diamy) = getfar(diamx);
	dxcent = getcent(diamx, 0, diamy);
	ans = diam;
}

void calc_branches() {
	//map of branch sizes
	for (int i = 0; i < N; i++) {
		int d = min(getcent(diamx, 0, i), dxcent);
		setmin(ans, max(d, diam - d));
		distl[i] = d;
		mp[d]++;
	}

	//prefix sum
	int p = 0;
	for (auto it : mp) {
		p += it.se;
		psum[it.fi] = p;
	}
}

bool same (int a, int b) {
	return a == b || getcent(diamx, a, b) > distl[a];
}

bool has_balanced_hub() {
	vector<int> vlist, vbucket;

	//phase 1
	for (int leaf = 0; leaf < N; leaf++) {
		if (!vlist.empty() && same(vlist.back(), leaf)) {
			//same
			vbucket.push_back(leaf);
		} else {
			//not same
			vlist.push_back(leaf);
			if (!vbucket.empty()) {
				vlist.push_back(vbucket.back());
				vbucket.pop_back();
			}
		}
	}

	//phase 2
	int maj = vlist.back();

	while (!vlist.empty()) {
		if (same(vlist.back(), maj)) {
			if (vlist.size() == 1) {
				vbucket.push_back(vlist.back());
				vlist.pop_back();
			} else {
				vlist.pop_back();
				vlist.pop_back();
			}
		} else {
			vlist.pop_back();
			if (vbucket.empty()) {
				//there is no majority element
				break;
			}
			vbucket.pop_back();
		}
	}

	if (!vbucket.empty()) {
		return false;	//there is a majority element
	}

	//no majority element -- but may still not be OK
	for (auto it : mp) {
		int dl = it.fi, dr = diam - dl;
		if (max(dl, dr) == ans) {
			//check if this is balanced -- the branches are balanced, but the left/right w.r.t the diameter may not be
			int lsize = prev(psum.find(dl))->se;
			int csize = it.se;
			int rsize = N - lsize - csize;
			if (lsize <= N / 2 && rsize <= N / 2) {
				return true;
			}
		}
	}
	return false;
}

int hubDistance (int nnnnn, int shostakovich) {
	reset();
	N = nnnnn;

	calc_diam();
	calc_branches();
	return has_balanced_hub() ? ans : -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:166:33: warning: unused parameter 'shostakovich' [-Wunused-parameter]
 int hubDistance (int nnnnn, int shostakovich) {
                                 ^~~~~~~~~~~~

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