| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 302691 | user202729 | Towns (IOI15_towns) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// moreflags=grader.cpp
// really, who includes .c files in a .cpp one?
// ...
// definitely not an excuse for not learning classical algorithms properly.
#include "towns.h"
#include<vector>
int hubDistance(int number, int sub) {
int const A=0;
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);
auto const diameter=distanceB[A]=distanceA[B];
for(int other=1; other<number; ++other) if(other!=B)
distanceB[other]=getDistance(B, other);
// 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+diameter)%2==0);
groups[(sec+diameter-first)>>1].push_back({(first+sec-diameter)>>1, node});
}
assert(groups.at(0)==std::vector<int>{A});
assert(groups.at(diameter)==std::vector<int>{B}); // <-- technically have side effects
// (memory allocation and deallocation)
int radius=INT_MAX, hub=-1, hubDistanceB; bool LRbalanced=false;
{
int sumLeftGroupSize=0; // exclude current group. Only count leaves
int lastNode=-1, lastGroupSize, lastr, lastDistanceB;
for(auto const& [distanceB, group]: groups){
auto const [distancePath, node]=*std::min_element(begin(group), end(group));
auto const r=std::max(distanceB, diameter-distanceB); // only correct for nodes on some diameter
assert(distancePath==0); // node is on AB path
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
assert(lastNode>=0);
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);
hub=lastNode; hubDistanceB=lastDistanceB; LRbalanced=lastLRBalanced;
}
if(radius==r and curLRBalanced>=LRbalanced){ // if there are two, use the LRbalanced one
hub=node; hubDistanceB=distanceB; LRbalanced=curLRBalanced;
}
break;
}
lastNode=node; lastGroupSize=(int)group.size(); lastr=r; lastDistanceB=distanceB;
sumLeftGroupSize+=(int)group.size();
}
}
assert(radius!=INT_MAX);
if(sub<3){
return radius;
}
}