oj.uz

Submission #397155

# Submission time Handle Problem Language Result Execution time Memory
397155 2021-05-01T15:05:52 Z rainboy Towns (IOI15_towns) C
100 / 100
 23 ms 912 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 332 KB Output is correct
2 Correct 14 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 20 ms 380 KB Output is correct
5 Correct 22 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 332 KB Output is correct
2 Correct 14 ms 380 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 19 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB Output is correct
2 Correct 20 ms 380 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 20 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 332 KB Output is correct
2 Correct 23 ms 368 KB Output is correct
3 Correct 20 ms 372 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 372 KB Output is correct
2 Correct 20 ms 912 KB Output is correct
3 Correct 21 ms 872 KB Output is correct