//Flower_On_Stone
#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
const int MAX_N = 100005;
int subtreeSize[MAX_N];
int distToCentroid[MAX_N];
multiset<pair<int, int>> ms[3];
vector<int> childCentroid;
bool check(int a, int b, int c)
{
return (a == b + c || b == a + c || c == b + a);
}
vector<int> createFunTour(int numNode, int numQuery)
{
if (numNode == 2)
{
return vector<int>({0, 1});
}
int centroid = 0;
subtreeSize[0] = numNode;
for (int node = 1; node < numNode; node++)
{
subtreeSize[node] = attractionsBehind(0, node);
if (subtreeSize[node] >= numNode / 2 && subtreeSize[node] < subtreeSize[centroid])
{
centroid = node;
}
}
for (int node = 0; node < numNode; node++)
{
if (node != centroid)
{
distToCentroid[node] = hoursRequired(centroid, node);
}
if (distToCentroid[node] == 1)
{
ms[childCentroid.size()].insert(make_pair(1, node));
childCentroid.push_back(node);
}
}
for (int node = 0; node < numNode; node++)
{
if (distToCentroid[node] > 1)
{
bool ok = false;
for (int i = 0; i + 1 < childCentroid.size(); i++)
{
if (hoursRequired(node, childCentroid[i]) + 1 == distToCentroid[node])
{
ms[i].insert(make_pair(distToCentroid[node], node));
ok = true;
break;
}
}
if (!ok)
{
ms[childCentroid.size() - 1].insert(make_pair(distToCentroid[node], node));
}
}
}
vector<int> resuft;
pair<int, int> last = make_pair(-1, -1);
if (childCentroid.size() == 3)
{
while (true)
{
if (check(ms[0].size(), ms[1].size(), ms[2].size()))
{
int a = ms[0].size(), b = ms[1].size(), c = ms[2].size();
if (a + b == c)
{
for (auto x : ms[1])
{
ms[0].insert(x);
}
ms[1].swap(ms[2]);
}
else if (a + c == b)
{
for (auto x : ms[2])
{
ms[0].insert(x);
}
}
else
{
for (auto x : ms[2])
{
ms[1].insert(x);
}
}
break;
}
int maxSize = 0, id = 0;
pair<int, int> maxNode = make_pair(0, 0);
for (int i = 0; i < 3; i++)
{
if (ms[i].find(last) != ms[i].end() && ms[i].size())
{
if (ms[i].rbegin()->first > maxNode.first)
{
maxNode = *ms[i].rbegin();
id = i;
maxSize = ms[i].size();
}
else if (ms[i].rbegin()->first > maxNode.first && maxSize < ms[i].size())
{
maxNode = *ms[i].rbegin();
id = i;
maxSize = ms[i].size();
}
}
}
resuft.push_back(maxNode.second);
ms[id].erase(maxNode);
if (ms[id].size())
{
last = *ms[id].begin();
}
else
{
last = make_pair(-1, -1);
}
}
}
if (last == make_pair(-1, -1))
{
last = (ms[0].size() >= ms[1].size() ? *ms[1].begin() : *ms[0].begin());
}
while (ms[0].size() || ms[1].size())
{
if (ms[0].size() && ms[0].find(last) == ms[0].end())
{
last = *ms[0].begin();
resuft.push_back(ms[0].rbegin()->second);
ms[0].erase(*ms[0].rbegin());
}
else
{
last = *ms[1].begin();
resuft.push_back(ms[1].rbegin()->second);
ms[1].erase(*ms[1].rbegin());
}
}
resuft.push_back(centroid);
return resuft;
}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:52:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i + 1 < childCentroid.size(); i++)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fun.cpp:112:79: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | else if (ms[i].rbegin()->first > maxNode.first && maxSize < ms[i].size())
| ~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
