Submission #1296656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296656		vincentbucourt1	Towns (IOI15_towns)	C++20	0 / 100	9 ms	1852 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int hubDistance(int N, int subtask) {
	int maxDist = 0, diam1 = 0;
	for (int i = 1; i < N; i++) {
		int distOn = getDistance(0, i);
		if (distOn > maxDist) {
			maxDist = distOn, diam1 = i;
		}
	}
	vector<int> distDiam1(N, 0);
	for (int i = 0; i < N; i++) {
		distDiam1[i] = getDistance(diam1, i);
	}
	int diam2 = max_element(distDiam1.begin(), distDiam1.end()) - distDiam1.begin();
	vector<int> distDiam2(N, 0);
	for (int i = 0; i < N; i++) {
		distDiam2[i] = getDistance(diam2, i);
	}
	vector<int> distHor(N, 0), distVert(N, 0); // from diam1
	int maxMin = 0;
	for (int i = 0; i < N; i++) {
		assert(!((distDiam1[diam2] + distDiam2[i] - distDiam1[i])&1));
		distHor[i] = (distDiam1[diam2] + distDiam2[i] - distDiam1[i]) / 2;
		assert(!((3*distDiam2[i] - distDiam1[diam2] - distDiam1[i])&1));
		distVert[i] = (3*distDiam2[i] - distDiam1[diam2] - distDiam1[i]) / 2;
		maxMin = max(maxMin, min(distHor[i], distDiam1[diam2] - distHor[i]));
	}
	cerr << maxMin << "\n";
	return maxMin;
}

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