Submission #1174255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174255		sid03	Fun Tour (APIO20_fun)	C++20	100 / 100	238 ms	88080 KiB

fun

#include "fun.h"
#include <vector>
#include <queue>
#include <deque>
using namespace std;

int n,c,x,deg,cur,k;
int* d;
vector<int> p;
queue<int>* q;
vector<deque<int>> t;

void centroid() {
    c = 0;
    int ab = n;
    for (int i = 1; i < n; i++) {
        x = attractionsBehind(0,i);
        if (x >= n-n/2 && x < ab) {
            c = i;
            ab = x;
        }
    }
}

void centroidDistances() {
    d = new int[n];
    q = new queue<int>[n];
    d[c] = 0;
    for (int i = 0; i < n; i++) {
        if (i == c) continue;
        d[i] = hoursRequired(i,c);
        q[d[i]].push(i);
    }
}

void filter() {
    while (!q[1].empty()) {
        t.push_back(deque<int>());
        t.back().push_back(q[1].front());
        q[1].pop();
    }
    deg = t.size();
    for (int i = 2; i < n; i++) {
        while (!q[i].empty()) {
            for (int j = 0; j < deg; j++) {
                if (j == deg-1 || d[q[i].front()] == hoursRequired(t[j].front(), q[i].front()) + 1) {
                    t[j].push_back(q[i].front());
                    q[i].pop();
                    break;
                }
            }
        }
    }
}

void alternate() {
    deque<int> t0,t1;
    for (int i = 0; i < deg; i++) {
        if (i == k) continue;
        swap(t0,t1);
        while (!(t1.empty() && t[i].empty())) {
            if (!t[i].empty() && (t1.empty() || d[t[i].front()] + (i==cur) <= d[t1.front()])) {
                t0.push_back(t[i].front());
                t[i].pop_front();
            } else {
                t0.push_back(t1.front());
                t1.pop_front();
            }
        }
    }

    bool clast;
    if (t0.size() < t[k].size()) {
        t0.push_front(c);
        clast = 0;
    } else clast = 1;
    if (cur != k) swap(t0,t[k]);
    while (!t[k].empty()) {
        p.push_back(t[k].back());
        t[k].pop_back();
        p.push_back(t0.back());
        t0.pop_back();
    }
    if (clast) p.push_back(c);
}

void greedy() {
    int m = n, mxd = 0, mxts, nex;
    for (int i = 0; i < deg; i++) {
        if (d[t[i].back()] > mxd) {
            cur = i;
            mxd = d[t[i].back()];
        }
    }

    while (m > 2) {
        mxd = 0; mxts = 0;
        for (int i = 0; i < deg; i++) {
            if (t[i].size() > mxts) {
                k = i;
                mxts = t[i].size();
            }
            if (i != cur && !t[i].empty() && d[t[i].back()] > mxd) {
                nex = i;
                mxd = d[t[i].back()];
            }
        }

        if (d[t[cur].back()] >= mxd && m - mxts*2 <= 1) return;
        p.push_back(t[cur].back());
        t[cur].pop_back();
        cur = nex;
        m--;
    }
}

vector<int> createFunTour(int N, int Q) {
    if (N == 2) return vector<int>{0,1};
    n = N;
    centroid();
    centroidDistances();
    filter();
    greedy();
    alternate();
    return p;
}

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