Submission #1072864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072864		thinknoexit	Fun Tour (APIO20_fun)	C++17	47 / 100	421 ms	92236 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
set<pair<int, int>> s[N];
bool ch[N];
vector<int> createFunTour(int _N, int Q) {
    n = _N;
    if (n <= 500) {
        vector<bool> ch(n, false);
        vector<vector<int>> dis(n, vector<int>(n, 0));
        for (int i = 0;i < n;i++) {
            for (int j = i + 1;j < n;j++) {
                dis[i][j] = dis[j][i] = hoursRequired(i, j);
            }
        }
        int mx = 0, idx = 0;
        for (int i = 0;i < n;i++) {
            if (dis[0][i] > mx) {
                mx = dis[0][i];
                idx = i;
            }
        }
        vector<int> res;
        res.push_back(idx);
        ch[idx] = 1;
        for (int i = 1;i < n;i++) {
            int mx = 0, idx = 0;
            for (int j = 0;j < n;j++) {
                if (ch[j]) continue;
                if (dis[res.back()][j] > mx) {
                    mx = dis[res.back()][j];
                    idx = j;
                }
            }
            ch[idx] = 1;
            res.push_back(idx);
        }
        return res;
    }
    for (int i = n - 1;i >= 0;i--) {
        s[i].insert({ 0, i });
        if (2 * i + 1 < n) {
            for (auto& [d, j] : s[2 * i + 1]) s[i].insert({ d + 1, j });
        }
        if (2 * i + 2 < n) {
            for (auto& [d, j] : s[2 * i + 2]) s[i].insert({ d + 1, j });
        }
    }
    vector<int> res;
    res.push_back(n - 1);
    while ((int)res.size() < n) {
        int now = res.back();
        ch[now] = 1;
        auto x1 = (--s[now].end());
        int d = 0;
        int mx = x1->first, idx = x1->second;
        s[now].erase({ 0, now });
        while (now != 0) {
            int p = (now - 1) / 2;
            if (ch[p]) break;
            s[p].erase({ ++d, res.back() });
            int dis = d, id = 0;
            if (now == 2 * p + 1) {
                if (s[now + 1].empty()) id = p;
                else {
                    auto x = --s[now + 1].end();
                    dis += x->first, id = x->second;
                }
            }
            else {
                if (s[now - 1].empty()) id = p;
                else {
                    auto x = --s[now - 1].end();
                    dis += x->first, id = x->second;
                }
            }
            if (dis > mx) {
                mx = dis;
                idx = id;
            }
            now = p;
        }
        res.push_back(idx);
    }
    return res;
}

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