Submission #397155

#	Time	Username	Problem	Language	Result	Execution time	Memory
397155		rainboy	Towns (IOI15_towns)	C11	100 / 100	23 ms	912 KiB

towns

#include "towns.h"
#include <string.h>

#define N	110
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }

int dd[N][N];

int getDistance_(int i, int j) {
	if (dd[i][j] == -1)
		dd[i][j] = dd[j][i] = getDistance(i, j);
	return dd[i][j];
}

int hubDistance(int n, int sub) {
	static int dd0[N], ddu[N], xx[N], yy[N], kk[N];
	int u, v, i, i_, j_, d0u, duv, r_, kl, kr, k;

	for (i = 0; i < n; i++)
		memset(dd[i], -1, n * sizeof *dd[i]), dd[i][i] = 0;
	u = -1;
	for (i = 0; i < n; i++) {
		dd0[i] = getDistance_(0, i);
		if (u == -1 || dd0[u] < dd0[i])
			u = i;
	}
	d0u = dd0[u];
	v = -1;
	for (i = 0; i < n; i++) {
		ddu[i] = getDistance_(u, i);
		if (v == -1 || ddu[v] < ddu[i])
			v = i;
	}
	duv = ddu[v];
	for (i = 0; i < n; i++)
		xx[i] = (ddu[i] + d0u - dd0[i]) / 2, yy[i] = ddu[i] - xx[i];
	r_ = INF, i_ = -1, j_ = -1;
	for (i = 0; i < n; i++) {
		int r;

		if (xx[i] > xx[v])
			yy[i] += xx[i] - xx[v], xx[i] = xx[v];
		r = max(xx[i], duv - xx[i]);
		if (r_ > r)
			r_ = r, i_ = -1, j_ = -1;
		if (r_ == r) {
			if (i_ == -1 || xx[i_] == xx[i])
				i_ = i;
			else
				j_ = i;
		}
	}
	if (j_ != -1 && xx[j_] < xx[i_]) {
		kl = 0, kr = 0;
		for (i = 0; i < n; i++)
			if (xx[i] < xx[j_])
				kl++;
			else if (xx[i] > xx[j_])
				kr++;
		if (kl * 2 <= n && kr * 2 <= n)
			i_ = j_;
	}
	for (i = 0; i < n; i++)
		yy[i] += abs_(xx[i] - xx[i_]);
	memset(kk, 0, n * sizeof *kk);
	i_ = -1, k = 0;
	for (i = 0; i < n; i++)
		if (i_ == -1 || getDistance_(i_, i) != yy[i] + yy[i_]) {
			if (i_ == -1)
				i_ = i;
			k++, kk[i_]++;
		} else {
			kk[i]++;
			if (--k == 0)
				i_ = -1;
		}
	if (i_ == -1)
		return r_;
	k = 0;
	for (i = 0; i < n; i++)
		if (kk[i] > 0 && (i == i_ || getDistance_(i_, i) != yy[i] + yy[i_]))
			k += kk[i];
	return k * 2 <= n ? r_ : -r_;
}

Compilation message (stderr)

towns.c: In function 'hubDistance':
towns.c:23:23: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   23 |   memset(dd[i], -1, n * sizeof *dd[i]), dd[i][i] = 0;
      |                       ^
towns.c:68:18: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   68 |  memset(kk, 0, n * sizeof *kk);
      |                  ^
towns.c:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
   18 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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