Submission #785577

#	Time	Username	Problem	Language	Result	Execution time	Memory
785577		Sohsoh84	Towns (IOI15_towns)	C++17	13 / 100	20 ms	492 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 = 300 + 10;

int n, f[MAXN], sz[MAXN], dist[MAXN][MAXN];

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

inline int get(int u, int v) {
	return dist[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_;
	memset(sz, 0, sizeof sz);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			dist[i][j] = dist[j][i] = getDistance(i - 1, j - 1);

	int diam_v = diam_t(1).X;
	auto [diam_u, diam] = diam_t(diam_v);

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

		mp[du - dv].push_back(i);

		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.size();
	
		int mx = 0;
		vector<int> vec;
		for (int e : y) {
			vec.push_back(e);
			sz[e]++;
			for (int x : vec) {
				if (x == e) continue;
				
				if (get(e, x) + diam <= min(get(e, diam_u) + get(x, diam_v), get(e, diam_v) + get(x, diam_u))) {
					debug(x)
					sz[x]++;
					sz[e]--;
					vec.pop_back();
					break;
				}
			}
		}

		for (int e : y)
			mx = max(mx, sz[e]);

		if (x == -1 * tr || x == tr)
			if (ps <= n / 2 && ss <= n / 2 && mx <= n / 2)
				return r;

		ps += y.size();
	}

	return -r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:69:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |   ss -= y.size();
      |                ^
towns.cpp:76:13: warning: declaration of 'x' shadows a previous local [-Wshadow]
   76 |    for (int x : vec) {
      |             ^
towns.cpp:68:13: note: shadowed declaration is here
   68 |  for (auto [x, y] : mp) {
      |             ^
towns.cpp:96:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   96 |   ps += y.size();
      |                ^
towns.cpp:40:29: warning: unused parameter 'sub' [-Wunused-parameter]
   40 | int hubDistance(int N_, int sub) {
      |                         ~~~~^~~

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