Submission #96574

#	Time	Username	Problem	Language	Result	Execution time	Memory
96574		streifi	Towns (IOI15_towns)	C++14	25 / 100	20 ms	1092 KiB

towns

#include "towns.h"
#include <vector>
#include <iostream>
using namespace std;

const int MAX_DIST = 1e6+5;

vector< vector<int> > mat;

int get_dist(int a, int b) {
	if (mat[a][b] == -1)
		return mat[a][b] = mat[b][a] = getDistance(a, b);
	else
		return mat[a][b];
}


int hubDistance(int N, int sub) {
	mat.assign(N, vector<int>(N, -1));
	int u = -1;
	int mx = -1;
	for (int i = 0; i < N; ++i) {
		if (get_dist(0, i) > mx) {
			u = i;
			mx = get_dist(0, i);
		}
	}
	int v = -1;
	mx = -1;
	for (int i = 0; i < N; ++i) {
		if (get_dist(u, i) > mx) {
			v = i;
			mx = get_dist(u, v);
		}
	}
	//cout << u << " " << v << endl;
	vector<int> freq(mx+1, 0);
	for (int i = 0; i < N; ++i) {
		int k = get_dist(i, u);
		int l = get_dist(i, v);
		++freq[(mx+k-l)/2];
	}
	int ans = 0x3f3f3f3f;
	for (int i = 0; i < mx; ++i) {
		//cout << freq[i] << " ";
		if (freq[i])
			ans = min(ans, max(i, mx-i));
	}
	//cout << endl;
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

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