제출 #567917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567917		Stickfish	즐거운 행로 (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();
    }
}

컴파일 시 표준 에러 (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