제출 #1291781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291781		ortsac	도시들 (IOI15_towns)	C++20	39 / 100	11 ms	1852 KiB

towns

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

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

const int MAXN = 120;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dist[MAXN][MAXN];

int query(int a, int b) {
	if (a == b) return 0;
	if (a > b) swap(a, b);
	if (dist[a][b]) return dist[a][b];
	return (dist[a][b] = getDistance(a, b));
}

int32_t hubDistance(int32_t n, int32_t sub) {
	memset(dist, 0, sizeof dist);
	// achar diametro
	pii mx = {0, 0};
	for (int i = 1; i < n; i++) mx = max(mx, {query(1, i), i});
	int p1 = mx.se;
	mx = {0, 0};
	for (int i = 0; i < n; i++) mx = max(mx, {query(p1, i), i});
	int p2 = mx.se, diam = mx.fr;
	int mi = INF;
	vector<array<int, 2>> ab(n);
	vector<int> height(n);
	for (int i = 0; i < n; i++) {
		int apc = query(i, p1);
		int bpc = query(i, p2);
		int amc = (apc - bpc);
		int a = (amc + diam)/2, b = (diam - a);
		ab[i] = {a, b};
		height[i] = (apc - a);
		mi = min(mi, max(a, b));
	}
	// dividir em halfs
	vector<int> h(2);
	vector<vector<int>> c(2);
	for (int i = 0; i < n; i++) {
		int lado = 0;
		if (ab[i][0] > ab[i][1]) lado = 1;
		if (max(ab[i][0], ab[i][1]) == mi) c[lado].push_back(i);
		else h[lado]++;
	}
	int q = -1;
	if (c[0].size() > (n/2)) q = 0;
	else if (c[1].size() > (n/2)) q = 1;
	if (q != -1) {
		vector<int> x = c[q];
		int curr = 0, cnt = 0;
		for (auto u : x) {
			if (cnt == 0) {
				curr = u;
				cnt = 1;
			} else if (query(u, curr) < (height[u] + height[curr])) cnt++;
			else cnt--;
		}
		// curr is the goat
		cnt = 0;
		for (auto u : x) if (query(u, curr) < (height[u] + height[curr])) cnt++;
		if (cnt <= (n/2)) return mi;
		else return -mi;
	}
	// show, agora vamo ver se tem o centro bomzao
	int q1, q2;
	bool ok = 0;
	// testar com centro 1
	q1 = h[0], q2 = (h[1] + c[1].size());
	if (max({q1, q2}) <= (n/2)) ok = 1;
	// testar com centro 2
	q1 = (h[0] + c[0].size()), q2 = h[1];
	if (max({q1, q2}) <= (n/2)) ok = 1;
	// res
	if (!ok) mi *= -1;
	return mi;
}

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