| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 302712 |
2020-09-19T04:50:09 Z |
user202729 |
Towns (IOI15_towns) |
C++17 |
|
24 ms |
920 KB |
#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
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)
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
384 KB |
Output is correct |
| 2 |
Correct |
20 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
22 ms |
384 KB |
Output is correct |
| 5 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
384 KB |
Output is correct |
| 2 |
Correct |
16 ms |
384 KB |
Output is correct |
| 3 |
Correct |
23 ms |
384 KB |
Output is correct |
| 4 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
384 KB |
Output is correct |
| 2 |
Correct |
23 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
24 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
384 KB |
Output is correct |
| 2 |
Correct |
22 ms |
384 KB |
Output is correct |
| 3 |
Correct |
24 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
384 KB |
Output is correct |
| 2 |
Correct |
22 ms |
896 KB |
Output is correct |
| 3 |
Correct |
22 ms |
920 KB |
Output is correct |
