Submission #290672

#	Time	Username	Problem	Language	Result	Execution time	Memory
290672		Kastanda	Fun Tour (APIO20_fun)	C++11	10 / 100	4 ms	5248 KiB

fun

// M
#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int N = 100005;
int n, Centroid, H[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);
                }
        int mx = 0;
        for (int i = 0; i < k; i ++)
                mx = max(mx, (int)vec[i].size());
        assert(mx <= n / 2);
        for (int i = 0; i < k; i ++)
                sort(vec[i].begin(), vec[i].end(), [&](int v, int u){return H[v] < H[u];});

        int last = -1;
        vector < int > P;
        while (true)
        {
                int j = -1;
                for (int i = 0; i < k; i ++)
                        if (i != last && (j == -1 || vec[i].size() > vec[j].size()))
                                j = i;
                if (j == -1 || !vec[j].size())
                        break;
                P.push_back(vec[j].back());
                vec[j].pop_back();
                last = j;
        }
        P.push_back(Centroid);
        int Cnt = 0;
        for (int i = 0; i < k; i ++)
                if (vec[i].size())
                        Cnt ++;
        assert(Cnt <= 1);
        if (!Cnt)
                return P;
        int j = 0;
        while (!vec[j].size())
                j ++;
        assert((int)vec[j].size() == 1);
        P.push_back(vec[j].back());
        return P;
}

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