Submission #567917

#	Time	Username	Problem	Language	Result	Execution time	Memory
567917		Stickfish	Fun Tour (APIO20_fun)	C++17	26 / 100	283 ms	40136 KiB

fun

#include "fun.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int n;
map<pair<int, int>, int> dst;
map<pair<int, int>, int> subtr;

int distance(int u, int v) {
    if (u == v)
        return 0;
    if (dst.find({u, v}) != dst.end()) {
        return dst[{u, v}];
    }
    if (dst.find({v, u}) != dst.end()) {
        return dst[{v, u}];
    }
    return dst[{v, u}] = hoursRequired(u, v);
}

int subtree_size(int u, int v) {
    if (u == v)
        return n;
    if (subtr.find({u, v}) != subtr.end()) {
        return subtr[{u, v}];
    }
    return subtr[{u, v}] = attractionsBehind(u, v);
}

int find_maxdepth(int rt, vector<int> vs) {
    int ans = rt;
    int ansdepth = 0;
    for (auto v : vs) {
        int d = distance(rt, v);
        if (d > ansdepth) {
            ansdepth = d;
            ans = v;
        }
    }
    return ans;
}

vector<int> ans_dumb() {
    vector<int> ans;
    vector<int> vs(n);
    for (int i = 0; i < n; ++i)
        vs[i] = i;
    int rt = find_maxdepth(0, vs);
    ans.push_back(rt);
    vs.erase(lower_bound(vs.begin(), vs.end(), rt));
    while (vs.size()) {
        int nv = find_maxdepth(rt, vs);
        ans.push_back(nv);
        rt = nv;
        vs.erase(lower_bound(vs.begin(), vs.end(), nv));
    }
    return ans;
}

vector<int> createFunTour(int N, int Q) {
    n = N;
    if (n <= 500) {
        return ans_dumb();
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

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