Submission #1072851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072851		thinknoexit	Fun Tour (APIO20_fun)	C++17	0 / 100	2051 ms	5208 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];
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();
        s[now].erase({ 0, now });
        int d = 0;
        int mx = 0, idx = -1;
        while (now != 0) {
            int p = (now - 1) / 2;
            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;
            }
        }
        res.push_back(idx);
        now = idx;
    }
    return res;
}

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