Submission #397146

#	Time	Username	Problem	Language	Result	Execution time	Memory
397146		rainboy	Towns (IOI15_towns)	C11	61 / 100	20 ms	1120 KiB

towns

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

#define N	110
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
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 ddu[N], ddv[N], ii[N], xx[N], yy[N], kk[N];
	int u, v, i, i_, j_, d_, r_, k1, k2, k3;

	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++) {
		ddv[i] = i == 0 ? 0 : getDistance_(0, i);
		if (u == -1 || ddv[u] < ddv[i])
			u = i;
	}
	v = -1;
	for (i = 0; i < n; i++) {
		ddu[i] = i == u ? 0 : getDistance_(u, i);
		if (v == -1 || ddu[v] < ddu[i])
			v = i;
	}
	d_ = ddu[v];
	for (i = 0; i < n; i++)
		ddv[i] = i == v ? 0 : getDistance_(v, i);
	r_ = INF, i_ = -1, j_ = -1;
	for (i = 0; i < n; i++) {
		int r;

		xx[i] = (d_ + ddu[i] - ddv[i]) / 2, yy[i] = (ddu[i] + ddv[i] - d_) / 2;
		r = max(xx[i], d_ - 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;
		}
		ii[i] = i;
	}
	if (sub <= 2)
		return r_;
	k1 = 0, k2 = 0, k3 = 0;
	for (i = 0; i < n; i++)
		if (xx[i] < xx[i_])
			k1++;
		else if (xx[i] > xx[i_])
			k3++;
		else
			k2++;
	if (k1 * 2 > n || k3 * 2 > n) {
		if (j_ == -1)
			return -r_;
		i_ = j_;
		k1 = 0, k2 = 0, k3 = 0;
		for (i = 0; i < n; i++)
			if (xx[i] < xx[i_])
				k1++;
			else if (xx[i] > xx[i_])
				k3++;
			else
				k2++;
		if (k1 * 2 > n || k3 * 2 > n)
			return -r_;
	}
	if (sub == 4)
		return k2 * 2 <= n ? r_ : -r_;
	memset(kk, 0, n * sizeof *kk);
	j_ = -1, k2 = 0;
	for (i = 0; i < n; i++)
		if (xx[i] == xx[i_]) {
			if (j_ == -1 || getDistance_(j_, i) != yy[i] + yy[j_]) {
				if (j_ == -1)
					j_ = i;
				k2++, kk[j_]++;
			} else {
				kk[i]++;
				if (--k2 == 0)
					j_ = -1;
			}
		}
	if (j_ == -1)
		return r_;
	k2 = 0;
	for (i = 0; i < n; i++)
		if (kk[i] > 0 && (i == j_ || getDistance_(j_, i) != yy[i] + yy[j_]))
			k2 += kk[i];
	return k2 * 2 <= n ? r_ : -r_;
}

Compilation message (stderr)

towns.c: In function 'hubDistance':
towns.c:25:23: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   25 |   memset(dd[i], -1, n * sizeof *dd[i]), dd[i][i] = 0;
      |                       ^
towns.c:84:18: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   84 |  memset(kk, 0, n * sizeof *kk);
      |                  ^
towns.c:21:29: warning: variable 'ii' set but not used [-Wunused-but-set-variable]
   21 |  static int ddu[N], ddv[N], ii[N], xx[N], yy[N], kk[N];
      |                             ^~

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