Submission #561303

#	Time	Username	Problem	Language	Result	Execution time	Memory
561303		nghiass001	Fun Tour (APIO20_fun)	C++17	47 / 100	127 ms	15456 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, isans[maxN];
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;
    REP(i, 0, n) {
        int tmp = attractionsBehind(0, i);
        if (tmp >= (n + 1) / 2 && tmp < mini) u = i, mini = tmp;
    }

    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();
        }
    }

    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;
        }
    }

    REP(i, 0, n) if (!choice[i]) ++sz[all_next.size()], choice[i] = all_next.size();

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

    REP(i, 0, n) {
        List[choice[i]].push_back(i);
    }
    FOR(i, 1, 3)
        sort(List[i].begin(), List[i].end(), [] (int x, int y) { return depth[x] < depth[y]; });

    /// solve

    int type_now = 0;
    REP(step, 0, n) {
        int type_next = 0;
        if (sz[1] + sz[2] + 1 == sz[3]) type_next = 3;
        if (sz[1] + sz[3] + 1 == sz[2]) type_next = 2;
        if (sz[2] + sz[3] + 1 == sz[1]) 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()];
            }
        }
        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: 0 / 19
• Subtask 5: 0 / 34