Submission #349767

#	Time	Username	Problem	Language	Result	Execution time	Memory
349767		pit4h	Towns (IOI15_towns)	C++14	25 / 100	25 ms	1132 KiB

towns

#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int MAXN = 111;
int dist[MAXN][MAXN];
int n, subtask;
int hubDistance(int N, int sub) {
	int l = -1, r = -1;
	subtask = sub;
	n = N;
	for(int i=1; i<n; ++i) {
		dist[0][i] = getDistance(0, i);
		dist[i][0] = dist[0][i];
		if(l==-1 || dist[0][i] > dist[0][l]) {
			l = i;
		}
	}
	for(int i=0; i<n; ++i) {
		if(i==l) continue;
		dist[l][i] = getDistance(l, i);
		dist[i][l] = dist[l][i];
		if(r==-1 || dist[l][i] > dist[l][r]) {
			r = i;
		}
	}
	int R = 1e9+1;
	for(int i=0; i<n; ++i) {
		if(i==l || i==r) continue;
		dist[r][i] = getDistance(r, i);
		dist[i][r] = dist[r][i];
		int tmp = (dist[l][i] + dist[r][i] - dist[l][r])/2;
		R = min(R, max(dist[l][i] - tmp, dist[r][i] - tmp));
	}

	return R;
}

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