제출 #1291734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291734		ortsac	도시들 (IOI15_towns)	C++20	35 / 100	13 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);
	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};
		mi = min(mi, max(a, b));
	}
	// dividir em halfs
	vector<int> h(2), 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]++;
			//cout << i << " " << lado << "\n";
		}
		else h[lado]++;
	}
	// show, agora vamo ver se tem o centro bomzao
	int q1, q2, q3;
	bool ok = 0;
	// testar com centro 1
	q1 = h[0], q2 = (h[1] + c[1]), q3 = c[0];
	if (max({q1, q2, q3}) <= (n/2)) ok = 1;
	// testar com centro 2
	q1 = (h[0] + c[0]), q2 = h[1], q3 = c[1];
	if (max({q1, q2, q3}) <= (n/2)) ok = 1;
	//cout << q1 << " " << q2 << " " << q3 << "\n";
	// res
	if (!ok) mi *= -1;
	return mi;
}

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