oj.uz

Submission #982737

# Submission time Handle Problem Language Result Execution time Memory
982737 2024-05-14T16:53:12 Z crafticat Fun Tour (APIO20_fun) C++17
0 / 100
 0 ms 348 KB 
#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;
            }
        }
        if (path > pathLongest) {
            pathLongest = path;
            node = par[x];
        }
        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;
    dist[x] = 0;
    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 < 0) 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) {
        kill(x);
        int next = getLongest(x);
        next = go(next);
        x = next;
        ans.push_back(next);
    }
    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Tour is not fun
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Tour is not fun
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Tour is not fun
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Tour is not fun
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Tour is not fun
2 Halted 0 ms 0 KB -