Submission #302712

#	Time	Username	Problem	Language	Result	Execution time	Memory
302712		user202729	Towns (IOI15_towns)	C++17	100 / 100	24 ms	920 KiB

towns

#include "towns.h"
#include<algorithm>
#include<climits>
#include<map>
#include<vector>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

int hubDistance(int number, int sub) {
	int const A=0; // * must be 0, relied upon by some code below
	std::vector<int> distanceA(number);
	for(int other=1; other<number; ++other)
		distanceA[other]=getDistance(A, other);

	int const B=int(std::max_element(begin(distanceA), end(distanceA))-distanceA.begin());
	std::vector<int> distanceB(number);
	distanceB[A]=distanceA[B];
	for(int other=1; other<number; ++other) if(other!=B)
		distanceB[other]=getDistance(B, other);
	auto const diameter=*std::max_element(begin(distanceB), end(distanceB));

	// distance from B -> [(distance from path AB, node index)...]
	std::map<int, std::vector<std::pair<int, int>>> groups;
	for(int node=0; node<number; ++node){
		auto const first=distanceA[node], sec=distanceB[node];
		assert((first+sec+distanceA[B])%2==0);
		groups[(sec+distanceA[B]-first)>>1].push_back({(first+sec-distanceA[B])>>1, node});
	}
	assert((groups.at(0)==std::vector<std::pair<int, int>>{{0, B}}));
	assert((groups.at(distanceA[B])==std::vector<std::pair<int, int>>{{0, A}}));
	// ^ technically have side effects (memory allocation and deallocation)

	int radius=INT_MAX, hubDistanceB; bool LRbalanced=false;
	{
		int sumLeftGroupSize=0; // exclude current group. Only count leaves
		int lastGroupSize, lastr, lastDistanceB;
		for(auto const& [distanceB, group]: groups){
			auto const r=std::max(distanceB, diameter-distanceB); // only correct for nodes on some diameter

			if(distanceB*2>=diameter){
				// node and lastNode are on some diameter
				// but the next node might not be
				// compare node and lastNode. One of them is the hub

				radius=std::min(lastr, r);
				bool const lastLRBalanced=
					std::max(sumLeftGroupSize-lastGroupSize, number-sumLeftGroupSize)
					<=number/2;
				bool const curLRBalanced=
					std::max(sumLeftGroupSize, number-sumLeftGroupSize-(int)group.size())
					<=number/2;
				assert(not (lastLRBalanced and curLRBalanced));

				if(radius==lastr){
					assert(not LRbalanced);
					hubDistanceB=lastDistanceB; LRbalanced=lastLRBalanced;
				}
				if(radius==r and curLRBalanced>=LRbalanced){ // if there are two, use the LRbalanced one
					hubDistanceB=distanceB; LRbalanced=curLRBalanced;
				}

				break;
			}
			lastGroupSize=(int)group.size(); lastr=r; lastDistanceB=distanceB;
			sumLeftGroupSize+=(int)group.size();
		}
	}

	assert(radius!=INT_MAX);
	if(sub<3){
		return radius;
	}

	if(not LRbalanced) // definitely not balanced
		return -radius;

	struct Dom{
		int node;
		int count;
		int pathDistance;
	}; // dominance component info
	Dom dom{-1, 0, -1};

	auto const sameDomComponent=[&](int node, int pathDistance){
		assert(node!=dom.node);
		return getDistance(node, dom.node)<dom.pathDistance+pathDistance;
	};

	struct DomGroup{
		std::pair<int, int> up; // (pathDistance, node) -- really. Write a struct.
		int upCount;
		std::vector<std::pair<int, int>> down;
	};
	std::vector<DomGroup> domGroups;

	for(auto const [pathDistance, node]: groups.at(hubDistanceB)){
		if(dom.count==0){
			assert(domGroups.empty() or domGroups.back().upCount==(int)domGroups.back().down.size());
			domGroups.push_back({
				{pathDistance, node},
					1,
					{}
			});
			dom={node, 1, pathDistance};
		}else{
			if(sameDomComponent(node, pathDistance)){
				domGroups.back().upCount++;
				++dom.count;
			}else{
				domGroups.back().down.push_back({pathDistance, node});
				--dom.count;
				assert(dom.count>=0);
			}
		}
	}

	if(dom.count==0){
		// definitely balanced
		return radius;
	}

	// recount
	assert(domGroups.back().upCount>(int)domGroups.back().down.size());
	dom.count=domGroups.back().upCount; domGroups.pop_back();

	for(auto const& group: domGroups){
		if(sameDomComponent(group.up.second, group.up.first))
			dom.count+=group.upCount;
		else
			for(auto [pathDistance, node]: group.down)
				dom.count+=sameDomComponent(node, pathDistance);
	}

	return dom.count<=number/2 ? radius: -radius;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:39:36: warning: declaration of 'distanceB' shadows a previous local [-Wshadow]
   39 |   for(auto const& [distanceB, group]: groups){
      |                                    ^
towns.cpp:18:19: note: shadowed declaration is here
   18 |  std::vector<int> distanceB(number);
      |                   ^~~~~~~~~
towns.cpp:38:22: warning: 'lastr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |   int lastGroupSize, lastr, lastDistanceB;
      |                      ^~~~~
towns.cpp:49:31: warning: 'lastGroupSize' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |      std::max(sumLeftGroupSize-lastGroupSize, number-sumLeftGroupSize)
      |               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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