Submission #785519

#	Time	Username	Problem	Language	Result	Execution time	Memory
785519		Sohsoh84	Towns (IOI15_towns)	C++17	35 / 100	14 ms	364 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int n, f[MAXN];

inline int get(int u, int v) {
	u--, v--;
	return getDistance(u, v);
}

inline pll diam_t(int v) {
	int ans = v, ans_val = 0;
	for (int i = 1; i <= n; i++) {
		int t = get(v, i);
		f[i] = t;
		if (t > ans_val)
			ans = i, ans_val = t;
	}

	return {ans, ans_val};
}

int hubDistance(int N_, int sub) {
	n = N_;
	int diam_v = diam_t(1).X;
	auto [diam_u, diam] = diam_t(diam_v);

	int r = numeric_limits<int>::max();
	map<int, int> mp;
	for (int i = 1; i <= n; i++) {
		int du = get(diam_u, i);
		int dv = f[i];

		mp[du - dv]++;

		int diff = max(du, dv) - min(du, dv);
		int a = (diff + diam) / 2;

		r = min(r, a);
	}

	int tr = 2 * r - diam;

	int ps = 0;
	int ss = n;
	for (auto [x, y] : mp) {
		ss -= y;
		if (x == -1 * tr || x == tr)
			if (ps <= n / 2 && ss <= n / 2 && y <= n / 2)
				return r;

		ps += y;
	}

	return -r;
}

Compilation message (stderr)

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

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