Submission #96587

#	Time	Username	Problem	Language	Result	Execution time	Memory
96587		streifi	Towns (IOI15_towns)	C++14	25 / 100	25 ms	1912 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;
	bool bal;
	vector<int> cum(mx+2), cumr(mx+2);
	cum[0] = 0;
	cum[mx+1] = 0;
	for (int i = 0 ; i < mx; ++i) {
		cum[i+1] = cum[i]+freq[i];
		cumr[mx-i] = cumr[mx-i+1]+freq[mx-i];
	}
	for (int i = 0; i < mx; ++i) {
		//cout << freq[i] << " ";
		if (freq[i] && max(i, mx-i) <= ans) {
			if (max(i, mx-i) < ans) {
				ans = max(i, mx-i);
				bal = false;
			}
			if (!bal) {
				if (max(freq[i], max(cum[i], cumr[i])) <= N/2) bal = true;
			}
		}
	}
	//cout << endl;
	if (!bal) ans *= -1;
	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) {
                            ^~~
towns.cpp:65:2: warning: 'bal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (!bal) ans *= -1;
  ^~

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