Submission #333525

#	Time	Username	Problem	Language	Result	Execution time	Memory
333525		534351	Fun Tour (APIO20_fun)	C++17	31 / 100	147 ms	17272 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, C;

int dist(int a, int b)
{
    if (a == b) return 0;
    return hoursRequired(a, b);
}
int subtree(int a, int b)
{
    if (a == b) return N;
    return attractionsBehind(a, b);
}
vi createFunTour(int n, int q)
{
    N = n;
    int sz[N], dC[N], d[2][N];
    vi ans;
    vpi guys[3];
    int pos[N];
    if (N <= 2)
    {
        ans.resize(N);
        iota(ALL(ans), 0);
        return ans;
    }
    vi pts;
    //find the centroid. apparently this is the node with the smallest subtree size > N/2
    FOR(i, 0, N)
    {
        sz[i] = subtree(0, i);
    }
    C = -1;
    FOR(i, 0, N)
    {
        if (sz[i] < (N + 1)/2) continue;
        if (C == -1 || sz[i] < sz[C]) C = i;
    }
    FOR(i, 0, N)
    {
        dC[i] = dist(C, i);
        if (dC[i] == 1) pts.PB(i);
    }
    // for (int x : pts)
    // {
    //     cerr << x << ' ';
    // }
    // cerr << endl;
    FOR(i, 0, 2)
    {
        FOR(j, 0, N)
        {
            d[i][j] = dist(pts[i], j);
        }
    }
    FOR(i, 0, N)
    {
        if (i == C) continue;
        pos[i] = 2;
        if (d[0][i] == dC[i] - 1) pos[i] = 0;
        if (d[1][i] == dC[i] - 1) pos[i] = 1;
        guys[pos[i]].PB({dC[i], i});
    }
    FOR(i, 0, 3)
    {
        sort(ALL(guys[i]));
    }
    int lst = -1;
    FOR(i, 0, N - 1)
    {
        int guy = -1;
        if (SZ(guys[0]) > SZ(guys[1]) + SZ(guys[2])) guy = 0;
        else if (SZ(guys[1]) > SZ(guys[2]) + SZ(guys[0])) guy = 1;
        else if (SZ(guys[2]) > SZ(guys[0]) + SZ(guys[1])) guy = 2;
        else
        {
            FOR(i, 0, 3)
            {
                if (i == lst || guys[i].empty()) continue;
                if (guy == -1 || guys[i].back().fi > guys[guy].back().fi) guy = i;
            }
        }
        ans.PB(guys[guy].back().se);
        guys[guy].pop_back();
        assert(guy != lst);
        lst = guy;
        //find the farthest node.
    }
    ans.PB(C);
    // for (int x : ans)
    // {
    //     cerr << x << ' ';
    // }
    // cerr << endl;
    return ans;
}

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