Submission #134645

#	Time	Username	Problem	Language	Result	Execution time	Memory
134645		nvmdava	Towns (IOI15_towns)	C++17	25 / 100	21 ms	508 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int dv[200], du[200];
map<int, std::vector<int>> dis;

int hubDistance(int N, int sub) {
	int v = 0, u = 0;
	for(int i = 0; i < N; i++)
		dv[i] = getDistance(v, i);
	for(int i = 0; i < N; i++)
		if(dv[i] > dv[u])
			u = i;
	int D = dv[u], T = 0;
	for(int i = 0; i < N; i++){
		du[i] = getDistance(u, i);
		T = max(T, du[i]);
	}
	swap(v, u);
	swap(dv, du);
	int r = 1000000000;
	for(int i = 0; i < N; i++){
		int q = (D + dv[i] - du[i]) >> 1;
		r = min(r, max(q, T - q));
	}
	for(int i = 0; i < N; i++)
		dis[D + dv[i] - du[i]].push_back(i);
	int chk;
	if(dis.find(r * 2) != dis.end())
		chk = r * 2;
	else
		chk = (T - r) * 2;
	int c1 = 0, c2 = 0, c3 = 0;
	for(int i = 0; i < N; i++){
		if(D + dv[i] - du[i] < 2 * r) c1++;
		else if(D + dv[i] - du[i] > 2 * r) c2++;
		else c3++;
	}
	if(max(c1, max(c2, c3)) <= N / 2) return r;
	if(c1 > N / 2) return -r;
	if(c2 > N / 2){
		if(chk == r * 2 && dis.find((T - r) * 2) != dis.end()) chk = (T - r) * 2;
		else return -r;
		c1 = c2 = c3 = 0;
		for(int i = 0; i < N; i++){
			if(D + dv[i] - du[i] < 2 * r) c1++;
			else if(D + dv[i] - du[i] > 2 * r) c2++;
			else c3++;
		}
		if(c1 > N / 2 || c2 > N / 2)return -r;
	}

	vector<int> fer = dis[chk];
	vector<int> fer2;
	int sz = 0;
	while(fer.size() > 1){
		for(int i = sz * 2 - 1; i < fer.size(); i += sz * 2){
			if(getDistance(fer[i], fer[i - sz]) != dv[fer[i]] + du[fer[i - sz]] - D){
				fer2.push_back(i);
			}
		}
		sz = sz * 2;
		swap(fer2, fer);
		fer2.clear();
	}
	if(fer.empty()) return r;
	for(int& x : dis[chk]){
		if(getDistance(x, fer[0]) != dv[fer[0]] + du[x] - D) sz++;
	}
	if(sz > N / 2) return -r;
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:58:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = sz * 2 - 1; i < fer.size(); i += sz * 2){
                           ~~^~~~~~~~~~~~
towns.cpp:8:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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