Submission #394441

#	Time	Username	Problem	Language	Result	Execution time	Memory
394441		thuanqvbn03	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	332 KiB

fun

//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 (stderr)

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())
      |                                                                       ~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34