oj.uz

Submission #610251

# Submission time Handle Problem Language Result Execution time Memory
610251 2022-07-28T06:07:14 Z Temmie Towns (IOI15_towns) C++17
100 / 100
 18 ms 980 KB 
#include "towns.h"
#include <bits/stdc++.h>

int hubDistance(int n, int sub) {
	std::vector <std::vector <int>> am(n, std::vector <int> (n, 0));
	int u = -1, v = -1;
	for (int i = 1; i < n; i++) {
		am[0][i] = getDistance(0, i);
		if (am[0][i] > am[0][u]) {
			u = v = i;
		}
	}
	for (int i = 0; i < n; i++) {
		am[u][i] = getDistance(u, i);
		if (am[u][i] > am[u][v]) {
			v = i;
		}
	}
	int ans = 1 << 30;
	int a = -1;
	std::vector <int> b(n);
	std::pair <int, int> p = { ans, ans };
	for (int i = 0; i < n; i++) {
		b[i] = am[u][i] - am[0][i] + am[0][u];
		b[i] >>= 1;
		ans = std::min(ans, std::max(b[i], am[u][v] - b[i]));
		if (i && i != u) {
			p = { std::min(p.first, b[i]), std::max(p.second, b[i]) };
		}
	}
	for (int i = 0; i < n; i++) {
		if (ans != std::max(b[i], am[u][v] - b[i])) {
			continue;
		}
		int x = 0, y = 0;
		for (int j = 0; j < n; j++) {
			if (b[j] > b[i]) {
				y += b[j] != b[i];
			} else {
				x += b[j] != b[i];
			}
		}
		a = std::max(x, y) <= (n >> 1) ? i : a;
	}
	if (a == -1) {
		return -ans;
	}
	b[u] = p.first;
	b[0] = p.second;
	am[u][u] = b[u] << 1;
	int res = 0;
	int last = 0;
	std::vector <int> inc(n, 0);
	std::vector <bool> no(n, false);
	for (int i = 0; i < n; i++) {
		if (b[i] != b[a]) {
			continue;
		}
		if (res == 0) {
			for (int j = 0; j < n; j++) {
				no[j] = false;
			}
			last = i;
		}
		if (i == last || getDistance(i, last) < am[u][i] + am[u][last] - (b[a] << 1)) {
			inc[last]++;
			res++;
		} else {
			res--;
			inc[i] = no[i] = true;
		}
	}
	res = 0;
	for (int i = 0; i < n; i++) {
		res += inc[i] * (!no[i] && inc[i] && (i == last || getDistance(i, last) < am[u][i] + am[u][last] - (b[a] << 1)));
	}
	return res <= (n >> 1) ? ans : -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:4:28: warning: unused parameter 'sub' [-Wunused-parameter]
    4 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 11 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 16 ms 388 KB Output is correct
5 Correct 18 ms 380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 14 ms 392 KB Output is correct
3 Correct 13 ms 340 KB Output is correct
4 Correct 14 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 15 ms 852 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 14 ms 852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 316 KB Output is correct
2 Correct 16 ms 980 KB Output is correct
3 Correct 14 ms 828 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 14 ms 888 KB Output is correct
3 Correct 15 ms 852 KB Output is correct