Submission #785253

#	Time	Username	Problem	Language	Result	Execution time	Memory
785253		Sohsoh84	Towns (IOI15_towns)	C++17	25 / 100	14 ms	856 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++) {
		if (i == v) continue;
		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();
	for (int i = 1; i <= n; i++) {
		if (i == diam_u || i == diam_v) continue;
		int du = get(diam_u, i);
		int dv = f[i];

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

		r = min(r, a);
	}

	return r;
}

Compilation message (stderr)

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

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