Submission #1135821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135821		gyg	Towns (IOI15_towns)	C++20	26 / 100	34 ms	584 KiB

towns

// Note: 0-indexed, multiple tests

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define pii pair<int, int>
#define fir first 
#define sec second
#define vec vector 
const int N = 115, INF = 2e9;

int n;

map<pii, int> str;
int qry(int u, int v) {
	assert(min(u - 1, v - 1) >= 0 && max(u - 1, v - 1) < n);
	
	if (u > v) swap(u, v);
	if (u == v) return 0;
	if (str.count({u, v})) return str[{u, v}];
	return str[{u, v}] = getDistance(u - 1, v - 1);
}

arr<int, N> dst;
arr<int, N> a_dst, b_dst;
int fr(int u) {
	pii mx = {-1, -1};
	for (int v = 1; v <= n; v++)
		dst[v] = qry(u, v), mx = max(mx, {dst[v], v});
	assert(mx.sec != -1);
	return mx.sec;
}

map<int, vec<int>> cmp_mp;
vec<pair<int, vec<int>>> cmp;
vec<int> in_a, in_b;
bool lf(int id) {
	int sm = 1;
	for (int i = 0; i < id; i++) sm += cmp[i].sec.size();
	return (sm <= n / 2);
}
bool rg(int id) {
	int sm = 1;
	for (int i = cmp.size() - 1; i > id; i--) sm += cmp[i].sec.size();
	return (sm <= n / 2);
}

struct Dsj {
	arr<int, N> pr;
	arr<vec<int>, N> st;
	void intl() { 
		for (int u = 1; u <= n; u++)
			pr[u] = u, st[u] = {u};
	}
	void mrg(int u, int v) {
		u = pr[u], v = pr[v];
		if (u == v) return;
		for (int w : st[v]) 
			pr[w] = u, st[u].push_back(w);
	}
} dsj;
bool chck(int id) {
	dsj.intl();
	for (int u : cmp[id].sec) 
		for (int v : cmp[id].sec) 
			if (qry(u, v) != a_dst[u] + a_dst[v] - 2 * in_a[id]) dsj.mrg(u, v);
	for (int u : cmp[id].sec)
		if (u == dsj.pr[u] && dsj.st[u].size() > n / 2) return false;	
	return true;
}

void intl() {
	n = 0;
	str.clear();
	dst.fill(0);
	a_dst.fill(0), b_dst.fill(0);
	cmp_mp.clear();
	cmp.clear();
	in_a.clear(), in_b.clear();
}

int hubDistance(int _n, int _s) {
	intl();
	n = _n; 

	int a = fr(1);
	int b = fr(a);
	a_dst = dst;
	fr(b);
	b_dst = dst;

	for (int u = 1; u <= n; u++)
		if (u != a && u != b) cmp_mp[a_dst[u] - b_dst[u]].push_back(u);
	for (pair<int, vec<int>> x : cmp_mp) cmp.push_back(x);
	in_a.resize(cmp.size()), in_b.resize(cmp.size());
	
	pair<int, vec<int>> bst = {INF, {}};
	for (int i = 0; i < cmp.size(); i++) {
		in_a[i] = (cmp[i].fir + a_dst[b]) / 2;
	 	in_b[i] = (-cmp[i].fir + a_dst[b]) / 2;
		int vl = max(in_a[i], in_b[i]);
		if (vl < bst.fir) bst = {vl, {i}};
		else if (vl == bst.fir) bst.sec.push_back(i);
	}

	bool ok = false;

	if (bst.sec.size() == 1) ok = chck(bst.sec[0]) && lf(bst.sec[0]) && rg(bst.sec[0]);
	else {
		assert(bst.sec.size() == 2);
		if (!lf(bst.sec[0])) ok = false;
		else if (!rg(bst.sec[0])) ok = chck(bst.sec[1]);
		else ok = chck(bst.sec[0]);
	}
	
	return (ok ? bst.fir : -bst.fir);
}

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