Submission #561487

#	Time	Username	Problem	Language	Result	Execution time	Memory
561487		nghiass001	Fun Tour (APIO20_fun)	C++17	100 / 100	237 ms	20304 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int maxN = 1e5 + 5;
int n;
int depth[maxN], choice[maxN], sz[4];
vector<int> List[4];
vector<int> Ans;

vector<int> createFunTour(int n, int Q) {
    int u = 0, mini = n + 1;

    /// find centroid
    REP(i, 0, n) {
        int tmp = attractionsBehind(0, i);
        if (tmp >= (n + 1) / 2 && tmp < mini) u = i, mini = tmp;
    }

    /// get depth from centroid to another node
    vector<int> all_next;
    REP(i, 0, n) if (i != u) {
        depth[i] = hoursRequired(u, i);
        if (depth[i] == 1) {
            all_next.push_back(i);
            choice[i] = all_next.size();
        }
    }

    /// get which branch this node is in
    REP(j, 0, (int)all_next.size() - 1) {
        int node = all_next[j];
        choice[node] = j + 1;
        int tmp = sz[j + 1] = attractionsBehind(u, node);

        REP(i, 0, n) if (!choice[i] && i != u) {
            if (attractionsBehind(i, node) != tmp) choice[i] = j + 1;
        }
    }

    /// init size of each branch
    REP(i, 0, n) if (!choice[i]) ++sz[all_next.size()], choice[i] = all_next.size();

    /// add root to smallest branch
    int id = 1;
    FOR(i, 1, 3) if (sz[i] < sz[id]) id = i;
    choice[u] = id;
    ++sz[id];

    /// add node and sort depth for each branch
    REP(i, 0, n) {
        List[choice[i]].push_back(i);
    }
    FOR(i, 1, 3) {
        depth[n] = -1;
        List[i].push_back(n);
        sort(List[i].begin(), List[i].end(), [] (int x, int y) { return depth[x] < depth[y]; });
    }

    /// solve
    int type_now = 0;
    int pre_depth = 0;

    REP(step, 0, n) {
        int type_next = 0;
        if (sz[1] + sz[2] <= sz[3] && type_now != 3) {
            if (type_now == 0) type_next = 3;
            else if (pre_depth >= depth[List[type_now ^ 3].back()]) type_next = 3;
        }
        if (sz[1] + sz[3] <= sz[2] && type_now != 2) {
            if (type_now == 0) type_next = 2;
            else if (pre_depth >= depth[List[type_now ^ 2].back()]) type_next = 2;
        }
        if (sz[2] + sz[3] <= sz[1] && type_now != 1) {
            if (type_now == 0) type_next = 1;
            else if (pre_depth >= depth[List[type_now ^ 1].back()]) type_next = 1;
        }
        if (type_next == 0) {
            int len_max = -1;
            FOR(i, 1, 3) if (type_now != i && sz[i] && depth[List[i].back()] > len_max) {
                type_next = i;
                len_max = depth[List[i].back()];
            }
        }
        pre_depth = depth[List[type_next].back()];
        Ans.push_back(List[type_next].back());
        List[type_next].pop_back();
        --sz[type_next];
        type_now = type_next;
    }

    return Ans;
}

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