Submission #982730

#	Time	Username	Problem	Language	Result	Execution time	Memory
982730		crafticat	Fun Tour (APIO20_fun)	C++17	10 / 100	3 ms	348 KiB

fun

#include "bits/stdc++.h"

using namespace std;

int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);

struct dino {
    vector<bool> vis;
    int n;

    int find(int x) {
        int best = -1;
        int dist = 0;

        for (int i = 0; i < n; ++i) {
            if (vis[i]) continue;
            int d = hoursRequired(x,i);
            if (d > dist) {
                dist = d;
                best = i;
            }
        }
        return best;
    }

    std::vector<int> createFunTour(int N, int Q) {
        n = N;
        vis.resize(n);

        int x = find(0);
        vector<int> ans;
        ans.push_back(x);
        vis[x] = true;

        while (true) {
            x = find(x);
            if (x == -1) break;
            ans.push_back(x);
            vis[x] = true;
        }
        return ans;
    }
};

vector<vector<int>> g;
int n;
vector<int> dist;
vector<int> par;
vector<bool> vis;

void calcDist(int x, int p) {
    int longest = 0;
    for (auto child : g[x]) {
        if (child == p) continue;
        calcDist(child,x);
        longest = max(longest, dist[child] + 1);
    }
    dist[x] = longest;
}

int getLongest(int x) {
    int pathLongest = dist[x];
    int node = x;
    int path = 0;

    while (par[x] != -1 && !vis[par[x]]) {
        path++;
        for (auto child : g[par[x]]) {
            if (child == x || child == par[par[x]] || vis[child]) continue;
            if (path + dist[child] + 1 > pathLongest) {
                pathLongest = path + dist[child] + 1;
                node = child;
            }
        }
        x = par[x];
    }

    return node;
}
int go(int x) {
    int node = -1;
    int d = -1;

    for (auto child : g[x]) {
        if (child == par[x]) continue;
        if (vis[child]) continue;
        if (dist[child] > d) {
            d = dist[child];
            node = child;
        }
    }
    if (node == -1) return x;
    return go(node);
}

void kill(int x) {
    vis[x] = true;
    x = par[x];

    while (x != -1 && !vis[x]) {
        int longest = 0;
        for (auto child : g[x]) {
            if (child == par[x] || vis[child]) continue;
            calcDist(child,x);
            longest = max(longest, dist[child] + 1);
        }
        dist[x] = longest;
        x = par[x];
    }
}

std::vector<int> createFunTour(int N, int Q) {
    if (N < 100) return dino().createFunTour(N,Q);
    n = N;
    g.resize(N + 1);
    par.resize(N + 1,-1);
    dist.resize(N + 1);
    vis.resize(N + 1);

    for (int i = 1; i < N; ++i) {
        int p = (i - 1) / 2;
        g[p].push_back(i);
        par[i] = p;
        g[i].push_back(p);
    }
    calcDist(0,-1);

    vector<int> ans;
    int x = go(0);
    ans.push_back(x);

    for (int i = 0; i < N - 1; ++i) {
        int next = getLongest(x);
        kill(x);
        next = go(next);
        ans.push_back(next);
    }
    return ans;
}

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