Submission #587608

#	Time	Username	Problem	Language	Result	Execution time	Memory
587608		benson1029	Towns (IOI15_towns)	C++14	61 / 100	32 ms	896 KiB

towns

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

int dis0[200], disX[200], disY[200];
vector< pair<int,int> > mid2;
vector<int> mid;
int X, Y;

bool checkdiff(int a, int b) {
	int ad = (disX[Y] + disX[a] + disY[a]) / 2 - disX[Y];
	int bd = (disX[Y] + disX[b] + disY[b]) / 2 - disX[Y];
	if(getDistance(a, b) == ad+bd) return true;
	return false;
}

int hubDistance(int N, int sub) {
	X = 1;
	for(int i=1; i<N; i++) {
		dis0[i] = getDistance(0, i);
		if(dis0[i] > dis0[X]) {
			X = i;
		}
	}
	Y = 0;
	for(int i=0; i<N; i++) {
		if(i==X) continue;
		disX[i] = getDistance(X, i);
		if(disX[i] > disX[Y]) {
			Y = i;
		}
	}
	// diameter: X to Y
	for(int i=0; i<N; i++) {
		if(i==Y) continue;
		disY[i] = getDistance(Y, i);
	}
	int ans = 1e9;
	int C = 0;
	vector<int> Cs;
	for(int i=0; i<N; i++) {
		if(i==X || i==Y) continue;
		int sum = (disX[Y] + disX[i] + disY[i]) / 2;
		int tmp = max(sum - disX[i], sum - disY[i]);
		if(tmp < ans) {
			C = i;
			Cs.clear(); Cs.push_back(i);
			ans = tmp;
		} else if(tmp == ans) Cs.push_back(i);
	}
	if(sub <= 2) return ans;
	int compX = 1, compY = 1, oth = N - 2;
	int tmpC;
	for(int C: Cs) {
		int sumC = (disX[Y] + disX[C] + disY[C]) / 2;
		compX = 1; compY = 1; oth = N - 2;
		mid.clear();
		for(int i=0; i<N; i++) {
			if(i==X || i==Y) continue;
			int sum = (disX[Y] + disX[i] + disY[i]) / 2;
			if(sum - disY[i] < sumC - disY[C]) {
				compX++;
				oth--;
			} else if(sum - disX[i] < sumC - disX[C]) {
				compY++;
				oth--;
			} else mid.push_back(i);
		}
		tmpC = C;
		if(compX <= N/2 && compY <= N/2) break;
	}
	C = tmpC;
	if(sub==4) {
		if(compX <= N/2 && compY <= N/2 && oth <= N/2) return ans;
		else return -ans;
	} else if(sub >= 3) {
		mid2.clear();
		for(int i=0; i<mid.size(); i++) mid2.push_back({mid[i], 1});
		while(mid2.size() >= 2) {
			vector< pair<int,int> > tmp;
			tmp.clear();
			for(int i=0; i<mid2.size()-1; i+=2) {
				if(checkdiff(mid2[i].first, mid2[i+1].first)) {
					if(mid2[i].second > mid2[i+1].second) {
						tmp.push_back(mid2[i]);
					} else if(mid2[i+1].second > mid2[i].second) {
						tmp.push_back(mid2[i+1]);
					}
				} else {
					tmp.push_back({mid2[i].first, mid2[i].second + mid2[i+1].second});
				}
			}
			if(mid2.size()%2==1) tmp.push_back(mid2[mid2.size()-1]);
			mid2 = tmp;
		}
		if(mid2.size() == 1) {
			int cnt = 0;
			for(int i:mid) {
				if(!checkdiff(i, mid2[0].first)) {
					cnt++;
				}
			}
			if(cnt > N/2 || compX > N/2 || compY > N/2) return -ans;
			else return ans;
		}
		if(compX > N/2 || compY > N/2) return -ans;
		return ans;
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:10: warning: declaration of 'C' shadows a previous local [-Wshadow]
   54 |  for(int C: Cs) {
      |          ^
towns.cpp:39:6: note: shadowed declaration is here
   39 |  int C = 0;
      |      ^
towns.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0; i<mid.size(); i++) mid2.push_back({mid[i], 1});
      |                ~^~~~~~~~~~~
towns.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for(int i=0; i<mid2.size()-1; i+=2) {
      |                 ~^~~~~~~~~~~~~~
towns.cpp:39:6: warning: variable 'C' set but not used [-Wunused-but-set-variable]
   39 |  int C = 0;
      |      ^

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