Submission #1232922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232922		LucaIlie	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	15 ms	480 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 256;
int n;
vector<int> comp[MAX_N];
int parent[MAX_N];
bool inPath[MAX_N];
mt19937 rnd(200);

int findParent(int v) {
    if (parent[v] != v)
        parent[v] = findParent(parent[v]);
    return parent[v];
}

void connect(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    // printf("connect %d %d\n", u, v);
    if (u == v)
        return;

    for (int x: comp[v])
        comp[u].push_back(x);
    comp[v].clear();
    parent[v] = u;
}

pair<int, int> getEdge(vector<int> a, vector<int> b) {
    if (a.size() == 1 && b.size() == 1)
        return {a[0], b[0]};

    vector<int> c, d;
    if (a.size() == 1) {
        for (int i = 0; i < (int)b.size() / 2; i++)
            c.push_back(b[i]);
        for (int i = (int)b.size() / 2; i < (int)b.size(); i++)
            d.push_back(b[i]);

        if (are_connected(a, d))
            return getEdge(a, d);
        return getEdge(a, c);
    }

    for (int i = 0; i < (int)a.size() / 2; i++)
        c.push_back(a[i]);
    for (int i = (int)a.size() / 2; i < (int)a.size(); i++)
        d.push_back(a[i]);

    if (are_connected(c, b))
        return getEdge(c, b);
    return getEdge(d, b);
}

pair<int, int> getEdgeBrute(vector<int> a, vector<int> b) {
    int last = -1;
    for (int v: b) {
        for (int x: comp[v])
            assert(a[0] != x);
        if (are_connected(a, comp[v]))
            return getEdge(a, comp[v]);

        if (last != -1)
            connect(last, v);
        last = v;
    }
    return {0, 0};
}

void shiftRight(vector<int> &v) {
    int aux = v.back();
    for (int i = v.size() - 1; i >= 1; i--)
        v[i] = v[i - 1];
    v[0] = aux;
}

void check(vector<int> v) {
    for (int i = 0; i < (int)v.size() - 1; i++)
        assert(are_connected({v[i]}, {v[i + 1]}));
}

vector<int> longest_trip(int N, int D) {
    n = N;

    vector<int> perm(n, 0);
    for (int i = 0; i < n; i++) {
        perm[i] = i, parent[i] = i;
        comp[i].clear();
        comp[i].push_back(i);
        inPath[i] = false;
    }
    shuffle(perm.begin(), perm.end(), rnd);

    vector<int> path(1, perm[0]);
    inPath[perm[0]] = true;
    while ((int)path.size() < n) {
        vector<int> allOut, cliqueOut;
        // for (int v: path)
        //     inPath[v] = true;
        for (int v = 0; v < n; v++) {
            if (inPath[v])
                continue;

            // printf("%d %d\n", v, findParent(v));
            if (findParent(v) == v)
                cliqueOut.push_back(v);
            allOut.push_back(v);
        }
        // printf("%d\n", path.back());

        // printf("INCEP %d\n");

        if (!are_connected({path.back()}, allOut)) {
            if (!are_connected(path, allOut)) {
                if (path.size() > allOut.size())
                    return path;
                return allOut;
            }

            auto e = getEdge(path, allOut);
            if (e.first == path[0])
                reverse(path.begin(), path.end());
            else {
                while (path.back() != e.first) 
                    shiftRight(path);
            }

            path.push_back(e.second);
            for (int v: allOut) {
                inPath[v] = true;
                if (v != e.second) 
                    path.push_back(v);
            }
            continue;
        }

        // for (int i = 0; i < (int)path.size(); i++)
        //     printf("%d ", path[i]);
        // printf("\n");
        auto e = getEdgeBrute({path.back()}, cliqueOut);
        // printf("%d\n", e.second);
        path.push_back(e.second);
        for (int v: comp[findParent(e.second)]) {
            // printf("%d\n", v);
            inPath[v] = true;
            if (v != e.second)
                path.push_back(v);
        }
        // printf("GATA %d\n\n\n\n", comp[42].size());
    }

    return path;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 30 / 60