Submission #290723

#	Time	Username	Problem	Language	Result	Execution time	Memory
290723		Kastanda	Fun Tour (APIO20_fun)	C++11	100 / 100	518 ms	50800 KiB

fun

// M
#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int N = 100005;
int n, Centroid, H[N], B[N];
map < int , int > MP[N];
inline int GetDist(int i, int j)
{
        if (i == j)
                return 0;
        if (MP[i][j])
                return MP[i][j];
        MP[i][j] = MP[j][i] = hoursRequired(i, j);
        return MP[i][j];
}

vector < int > createFunTour(int _n, int Q)
{
        n = _n;
        Centroid = 0;
        for (int i = 1; i < n; i ++)
                if (attractionsBehind(Centroid, i) * 2 > n)
                        Centroid = i;

        vector < int > Ch, vec[3];
        for (int i = 0; i < n; i ++)
                H[i] = GetDist(Centroid, i);
        for (int i = 0; i < n; i ++)
                if (H[i] == 1)
                        Ch.push_back(i);
        assert((int)Ch.size() <= 3);
        int k = (int)Ch.size();
        for (int i = 0; i < n; i ++)
                if (H[i] >= 1)
                {
                        int j = 0;
                        while (j + 1 < k && H[i] != GetDist(Ch[j], i) + 1)
                                j ++;
                        vec[j].push_back(i);
                }
        for (int i = 0; i < k; i ++)
                sort(vec[i].begin(), vec[i].end(), [&](int v, int u){return H[v] < H[u];});

        B[Centroid] = -1;
        for (int i = 0; i < k; i ++)
                for (int v : vec[i])
                        B[v] = i;

        int last = -1;
        vector < int > P;
        while (true)
        {
                int mx = 0;
                for (int i = 0; i < k; i ++)
                        mx = max(mx, (int)vec[i].size());
                int sm = 0;
                for (int i = 0; i < k; i ++)
                        sm += (int)vec[i].size();
                if (!sm)
                        break;
                if (mx >= sm - mx)
                {
                        int j = -1;
                        assert(mx <= sm - mx + 1);
                        for (int i = 0; i < k; i ++)
                                if ((int)vec[i].size() == mx)
                                        j = i;
                        assert(j != last && j != -1);
                        vec[0].swap(vec[j]);
                        vector < int > tmp;
                        for (int a : vec[1]) tmp.push_back(a);
                        for (int a : vec[2]) tmp.push_back(a);
                        sort(tmp.begin(), tmp.end(), [&](int v, int u){return H[v] < H[u];});
                        if (tmp.size() && H[vec[0].back()] < H[tmp.back()] && P.size() && B[P.back()] != B[tmp.back()])
                                tmp.swap(vec[0]);
                        while (tmp.size() && vec[0].size())
                        {
                                P.push_back(vec[0].back());
                                vec[0].pop_back();
                                P.push_back(tmp.back());
                                tmp.pop_back();
                        }
                        if (vec[0].size())
                        {
                                assert((int)vec[0].size() == 1);
                                P.push_back(vec[0][0]);
                                P.push_back(Centroid);
                        }
                        else if (tmp.size())
                        {
                                assert((int)tmp.size() == 1);
                                P.push_back(Centroid);
                                P.push_back(tmp[0]);
                        }
                        else
                                P.push_back(Centroid);
                        assert((int)P.size() == n);

                        for (int i = 0; i + 1 < n; i ++)
                                assert(B[P[i]] != B[P[i + 1]]);

                        return P;
                }
                int j = -1, h = -1;
                for (int i = 0; i < k; i ++)
                        if (i != last && vec[i].size() && h < H[vec[i].back()])
                                h = max(h, H[vec[i].back()]), j = i;
                /*for (int i = 0; i < k; i ++)
                        if (i != last && vec[i].size() && H[vec[i].back()] == h && (j == -1 || vec[i].size() > vec[j].size()))
                                j = i;*/
                assert(j != -1 && j != last);
                if (P.size() > 1)
                        assert(H[P[(int)P.size() - 2]] >= H[vec[j].back()]);
                P.push_back(vec[j].back());
                vec[j].pop_back();
                last = j;
        }
        assert(0);
}

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