Submission #790279

#	Time	Username	Problem	Language	Result	Execution time	Memory
790279		Sohsoh84	Towns (IOI15_towns)	C++17	100 / 100	16 ms	360 KiB

towns

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

using namespace std;

typedef pair<int, int> pll;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 300 + 10;

int n, D0[MAXN], D1[MAXN], diam, diam_v, diam_u;

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

inline int mirror_on_0u(int v) {
	return (D1[v] - D0[v] + D0[diam_u]) / 2;
}

inline bool is_eq(int a, int b) {
	return get(a, b) + D0[diam_u] < min(D0[a] + D1[b], D0[b] + D1[a]);
}

inline bool find_maj(vector<int> vec) {
	if (int(vec.size()) <= n / 2) return false;	

	vector<pll> R;

	int maj_cnt = 0;
	int maj = -1;

	if (vec.size() % 2 == 1) {
		maj_cnt = 1;
		maj = vec.back();
		vec.pop_back();
		
		R.push_back({maj, 1});
	}


	while (!vec.empty()) {
		int a = vec.back();
		vec.pop_back();
		int b = vec.back();
		vec.pop_back();

		if (is_eq(a, b)) {
			if (maj_cnt == 0) {
				maj = a;
				maj_cnt = 2;
			} else if (!is_eq(maj, a)) {
				if (maj_cnt == 1) {
					maj = a;
					maj_cnt = 1;
				} else if (maj_cnt == 2) {
					maj = -1;
					maj_cnt = 0;
				} else {
					maj_cnt -= 2;
				}
			} else maj_cnt += 2;

			R.push_back({a, 2});
		} else {
			R.push_back({a, 1});
			R.push_back({b, 1});
		}
	}
	
	if (maj >= 0) {
		int cnt = 0;
		for (auto [x, w] : R)
			if (x == maj || is_eq(maj, x))
				cnt += w;	

		return cnt > n / 2;
	}

	return false;

}

// TODO: n / 2 tof


int hubDistance(int N_, int sub) {
	memset(D0, 0, sizeof D0);
	memset(D1, 0, sizeof D1);

	n = N_;
	for (int i = 1; i < n; i++)
		D0[i] = get(0, i);

	map<int, vector<int>> mp;

	diam_u = max_element(D0, D0 + n) - D0;
	D1[0] = D0[diam_u];
	for (int i = 1; i < n; i++) {
		if (i == diam_u) continue;
		D1[i] = get(diam_u, i);
	}

	diam_v = max_element(D1, D1 + n) - D1;
	diam = D1[diam_v];

	int v_mir = mirror_on_0u(diam_v), r = numeric_limits<int>::max();
	vector<int> cent;
	for (int i = 0; i < n; i++) {
		if (mirror_on_0u(i) > v_mir) continue;
		int a = mirror_on_0u(i);
		int b = D1[diam_v] - mirror_on_0u(i);

		int tr = max(a, b);
		if (tr < r) {
			cent.clear();
			cent.push_back(a);
			r = tr;
		} else if (tr == r) cent.push_back(a);
	
		mp[a].push_back(i);
	}

	r = -r;

	sort(all(cent));
	cent.resize(unique(all(cent)) - cent.begin());	

	int ps = 0, ss = n;
	for (auto [x, vec] : mp) {	
		ss -= vec.size();
		if (find(all(cent), x) != cent.end()) {
			if (!find_maj(vec) && ps <= n / 2 && ss <= n / 2)
				r = abs(r);
		}

		ps += vec.size();
	}

	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  102 |  diam_u = max_element(D0, D0 + n) - D0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:109:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  109 |  diam_v = max_element(D1, D1 + n) - D1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:136:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  136 |   ss -= vec.size();
      |                  ^
towns.cpp:142:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  142 |   ps += vec.size();
      |                  ^
towns.cpp:92:29: warning: unused parameter 'sub' [-Wunused-parameter]
   92 | int hubDistance(int N_, int sub) {
      |                         ~~~~^~~

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