Submission #1072721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072721		thinknoexit	Fun Tour (APIO20_fun)	C++17	26 / 100	9 ms	3932 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
vector<int> adj[N];
vector<int> res;
int deg[N];
bool ch[N];
void dfs(int v, vector<int>& node, int p = -1) {
    node.push_back(v);
    for (auto& x : adj[v]) {
        if (x == p || ch[x]) continue;
        dfs(x, node, v);
    }
}
void dnc(int v) {
    vector<int> l, r;
    bool __ = 0;
    for (auto& x : adj[v]) {
        if (ch[x]) continue;
        if (!__) dfs(x, l, v), __ = 1;
        else dfs(x, r, v);
    }
    sort(l.rbegin(), l.rend()), sort(r.rbegin(), r.rend());
    int sz = r.size();
    for (int i = 0;i < sz;i++) {
        res.push_back(l[i]);
        res.push_back(r[i]);
        ch[l[i]] = ch[r[i]] = 1;
    }
    res.push_back(v);
    ch[v] = 1;
    if (l.size() == r.size()) return;
    dnc(l.back());
}
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 = 1;i < n;i++) {
        adj[i].push_back((i - 1) / 2);
        adj[(i - 1) / 2].push_back(i);
    }
    dnc(0);
    return res;
}

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