Submission #561066

#	Time	Username	Problem	Language	Result	Execution time	Memory
561066		piOOE	Fun Tour (APIO20_fun)	C++17	26 / 100	2074 ms	13132 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)

const int N = 100000;
vector<int> g[N];
int sz[N];
set<int> st[N], stt[N];
int depth[N];
bool used[N];

void calc_sz(int v, int p) {
    sz[v] = 1;
    for (int to: g[v]) {
        if (to != p && !used[to]) {
            calc_sz(to, v);
            sz[v] += sz[to];
        }
    }
}

int centroid(int v, int p, int n) {
    for (int to: g[v]) {
        if (to != p && !used[to] && sz[to] * 2 > n)
            return centroid(to, v, n);
    }
    return v;
}

void dfs(int v, int p, int leader) {
    depth[v] = depth[p] + 1;
    st[leader].insert(v);
    stt[leader].insert(v);
//    cout << v << " " << depth[v] << endl;
    for (int to: g[v]) {
        if (to != p) {
            dfs(to, v, leader);
        }
    }
}

vector<int> createFunTour(int n, int q) {
    const int infI = 1e9 + 7;
    if (n <= 500) {
        vector<vector<int>> dist(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                dist[i][j] = dist[j][i] = hoursRequired(i, j);
            }
        }
        int j = 0;
        pair<int, int> mxx = {-infI, -infI};
        for (; j < n; ++j) {
            mxx = max(mxx, make_pair(dist[j][0], j));
        }
        j = mxx.second;
        vector<int> ans;
        vector<bool> usd(n);
        int lst = infI;
        for (int k = 0; k < n; ++k) {
            ans.push_back(j);
            usd[j] = true;
            pair<int, int> mx = {-infI, -infI};
            for (int z = 0; z < n; ++z) {
                if (!usd[z] && dist[j][z] <= lst) {
                    mx = max(mx, make_pair(dist[j][z], z));
                }
            }
            if (mx.first == -infI) {
                break;
            }
            lst = mx.first;
            j = mx.second;
        }
        if (ans.size() == n) {
            return ans;
        }
        assert(false);
        return {};
    } else {
        for (int i = 1; i < n; ++i) {
            g[i].push_back((i - 1) >> 1);
            g[(i - 1) >> 1].push_back(i);
        }
        calc_sz(0, -1);
        int c = centroid(0, -1, n);
        auto cmp = [](int i, int j) {
            if (st[i].empty() && st[j].empty()) return i < j;
            else if (st[i].empty()) return false;
            else if (st[j].empty()) return true;
            else {
                int a = *st[i].rbegin(), b = *st[j].rbegin();
                if (depth[a] != depth[b]) return depth[a] > depth[b];
                return i < j;
            }
        };
        set<int, decltype(cmp)> nw(cmp);
        for (int to: g[c]) {
            dfs(to, c, to);
            nw.insert(to);
        }
        vector<int> ans;
        int mv = 1;
        while (!nw.empty()) {
            int a = *nw.begin();
//            cout << nw.size() << endl;
            if (st[a].empty()) {
                break;
            }
            if (ans.empty() || !stt[a].count(ans.back())) {
                nw.erase(a);
                ans.push_back(*st[a].rbegin());
                st[a].erase(prev(st[a].end()));
//                cout << nw.size() << endl;
                if (!st[a].empty())
                    nw.insert(a);
            } else {
                if (nw.size() < 2) {
                    while (1) {}
                }
                assert(nw.size() > 1);
                int b = *next(nw.begin());
                assert(!st[b].empty());
                a = b;
                nw.erase(a);
                ans.push_back(*st[a].rbegin());
                st[a].erase(prev(st[a].end()));
                if (!st[a].empty())
                    nw.insert(a);
            }
        }
        ans.push_back(c);
        return ans;
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:81:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if (ans.size() == n) {
      |             ~~~~~~~~~~~^~~~
fun.cpp:109:13: warning: unused variable 'mv' [-Wunused-variable]
  109 |         int mv = 1;
      |             ^~

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