Submission #134440

#	Time	Username	Problem	Language	Result	Execution time	Memory
134440		nvmdava	Towns (IOI15_towns)	C++17	25 / 100	22 ms	504 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;
	}

	vector<int> fer = dis[chk];
	vector<int> rep;
	return r;
	int i;
	for(i = 1; i < fer.size(); i++){
		if(getDistance(fer[i], fer[i - 1]) == dv[fer[i]] + du[fer[i - 1]] - D){
			rep.push_back(i - 1);
			rep.push_back(i);
			i++;
		}

	}
	if(i == fer.size() + 1) return r;
	int sz = fer.size() - rep.back() - 1, l = 0;
	for(int& x : rep){
		if(getDistance(fer[x], fer.back()) != dv[fer[x]] + du[fer.back()] - D){
			sz += x - l;
		}
		l = x;
	}
	if(sz > N / 2) return -r;
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 1; i < fer.size(); i++){
             ~~^~~~~~~~~~~~
towns.cpp:59:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i == fer.size() + 1) return r;
     ~~^~~~~~~~~~~~~~~~~
towns.cpp:60:35: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int sz = fer.size() - rep.back() - 1, l = 0;
           ~~~~~~~~~~~~~~~~~~~~~~~~^~~
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