제출 #396864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396864		rainboy	도시들 (IOI15_towns)	C11	61 / 100	25 ms	332 KiB

towns

#include "towns.h"
#include <stdio.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 hubDistance(int n, int sub) {
	static int ddu[N], ddv[N], ii[N], xx[N], yy[N];
	int u, v, i, i_, j_, d_, r_, k1, k2, k3;

	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_;
	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_])
				j_ = i, k2++;
			else {
				if (--k2 == 0)
					j_ = -1;
			}
		}
	if (j_ == -1)
		return r_;
	k2 = 0;
	for (i = 0; i < n; i++)
		if (xx[i] == xx[i_] && getDistance(j_, i) != yy[i] + yy[j_])
			k2++;
	return k2 * 2 <= n ? r_ : -r_;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.c: In function 'hubDistance':
towns.c:12:29: warning: variable 'ii' set but not used [-Wunused-but-set-variable]
   12 |  static int ddu[N], ddv[N], ii[N], xx[N], yy[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