Submission #785496

# Submission time Handle Problem Language Result Execution time Memory
785496 2023-07-17T09:39:05 Z Sohsoh84 Sorting (IOI15_sorting) C++17
Compilation error
0 ms 0 KB
#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();

	map<int, int> mp;
	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];

		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 == r || x == tr)
			if (ps <= n / 2 && ss <= n / 2 && y <= n / 2)
				return r;

		ps += y;
	}

	return -r;
}

Compilation message

sorting.cpp:1:10: fatal error: towns.h: No such file or directory
    1 | #include "towns.h"
      |          ^~~~~~~~~
compilation terminated.