Submission #52121

#	Time	Username	Problem	Language	Result	Execution time	Memory
52121		spencercompton	Towns (IOI15_towns)	C++17	25 / 100	22 ms	820 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance(int N, int sub) {
	pair<int, int > best = make_pair(-1,-1);
	//first is dist, second is ind
	for(int i = 1; i<N; i++){
		pair<int, int> now = make_pair(getDistance(0,i),i);
		best = max(best,now);
	}
	int first = best.second;
	best = make_pair(-1,-1);
	int A[N];
	int B[N];
	for(int i = 0; i<N; i++){
		if(i==first){
			continue;
		}
		pair<int, int> now = make_pair(getDistance(first,i),i);
		A[i] = now.first;
		best = max(best,now);
	}
	int second = best.second;
	int diameter = A[second];
	int inf = 100000000;
	int ans = inf;
	vector<vector<int> > li;
	int point = 0;
	int most = N/2;
	bool balanced = true;
	map<pair<int, int>, int> m;
	vector<int> ali;
	int x[N];
	for(int i = 0; i<N; i++){
		if(i==first || i==second){
			continue;
		}
		B[i] = getDistance(i,second);
		x[i] = (A[i]+B[i]-diameter)/2;
		int a = A[i]-x[i];
		int b = B[i]-x[i];
		pair<int, int> comb = make_pair(a,b);
		bool newer = false;
		if(m.find(comb)==m.end()){
			newer = true;
			m[comb] = point++;
			vector<int> xx;
			li.push_back(xx);
		}
		li[m[comb]].push_back(i);
		if(max(a,b)<ans){
			ans = max(a,b);
			ali.clear();
			ali.push_back(point-1);
		}
		else if(max(a,b)==ans && newer){
			ali.push_back(point-1);
		}
	}
	if(sub<=2){
		return ans;
	}
	for(int i = 0; i<li.size(); i++){
		if(li[i].size()>most){
			bool ishub = false;
			for(int j = 0; j<ali.size(); j++){
				ishub |= ali[j]==i;
			}
			if(!ishub){
				balanced =false;
				break;
			}
			int cur = li[i][0];
			int score = 1;
			for(int j = 1; j<li[i].size(); j++){
				if(score==0){
					cur = li[i][j];
					score = 1;
				}
				else if(getDistance(li[i][j],cur)==x[li[i][j]]+x[cur]){
					score--;
				}
				else{
					score++;
				}
			}
			if(score==0){
				break;
			}
			int cnt = 1;
			for(int j = 0; j<li[i].size(); j++){
				if(li[i][j]==cur){
					continue;
				}
				if(getDistance(li[i][j],cur)<x[li[i][j]]+x[cur]){
					cnt++;
				}
			}
			if(cnt > most){
				balanced = false;
			}
			break;
		}
	}
	if(!balanced){
		ans = -ans;
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
towns.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(li[i].size()>most){
      ~~~~~~~~~~~~^~~~~
towns.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j<ali.size(); j++){
                   ~^~~~~~~~~~~
towns.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 1; j<li[i].size(); j++){
                   ~^~~~~~~~~~~~~
towns.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j<li[i].size(); j++){
                   ~^~~~~~~~~~~~~

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