Submission #1249163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249163		hltk	Towns (IOI15_towns)	C++20	25 / 100	9 ms	328 KiB

towns

#include "towns.h"

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int hubDistance(int N, int sub) {
	vector<int> d1(N);
	for (int i = 0; i < N; ++i) {
		d1[i] = getDistance(0, i);
	}
	int x = max_element(d1.begin(), d1.end()) - d1.begin();
	vector<int> dx(N);
	for (int i = 0; i < N; ++i) {
		dx[i] = getDistance(x, i);
	}
	int y = max_element(dx.begin(), dx.end()) - dx.begin();
	vector<int> dy(N);
	for (int i = 0; i < N; ++i) {
		dy[i] = getDistance(y, i);
	}
	int d = dy[x];

	int R = 1e9;
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int distance_to_path = (dx[i] + dy[i] - d) / 2;
		int v1 = dx[i] - distance_to_path;
		int v2 = dy[i] - distance_to_path;
		if (v2 < v1) swap(v1, v2);
		if (v2 - v1 < R) {
			R = v2 - v1;
			ans = v2;
		}
	}

	return ans;
}

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