Submission #1226872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226872		chaeryeong	Towns (IOI15_towns)	C++20	25 / 100	10 ms	328 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance (int n, int sub) {
	int x = -1, v = 0;
	for (int i = 1; i < n; i++) {
		int s = getDistance(0, i);
		if (s > v)  {
			v = s; x = i;
		}
	}
	int y = -1, u = 0;
	vector <int> dist_x(n, 0);
	for (int i = 0; i < n; i++) {
		if (i != x) {		
			int s = getDistance(x, i);
			dist_x[i] = s;
			if (s > u) {
				u = s; y = i;
			}
		}
	}
	int w = 1e9;
	for (int i = 0; i < n; i++) {
		if (i != x && i != y) {
			int s = dist_x[i];
			int t = getDistance(y, i);
			w = min(w, abs(s - t));
		}
	}
	//x + y = u
	//x - y = w
	//x = (u + w) / 2;
	return (u + w) / 2;
}

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