Submission #1232901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232901		LucaIlie	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	6 ms	452 KiB

longesttrip

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

using namespace std;

const int MAX_N = 256;
int n;
mt19937 rnd(200);

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);
}

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;
    shuffle(perm.begin(), perm.end(), rnd);
    vector<int> path(1, perm[0]);
    vector<int> clique;
    for (int i = 1; i < n; i++) {
        int v = perm[i];

        if (!are_connected({path.back()}, {v})) {
            clique.push_back(v);
            continue;
        }

        path.push_back(v);
        if (clique.empty())
            continue;

        if (are_connected({v}, clique)) {
            pair<int, int> e = getEdge({v}, clique);
            path.push_back(e.second);
            for (int v: clique) {
                if (v == e.second) 
                    continue;
                // assert(are_connected({path.back()}, {v}));
                path.push_back(v);
            }
            clique.clear();
        }
    }

    if (clique.empty()) {
        // assert((int)path.size() == n);
        // check(path);
        return path;
    }

    if (!are_connected(path, clique)) {
        // assert((int)path.size() + (int)clique.size() == n);
        // check(path);
        // check(clique);
        if (path.size() > clique.size())
            return path;
        return clique;
    }


    pair<int, int> e;
    if (!are_connected({path.back()}, clique)) {
        e = getEdge(path, clique);
        // assert(are_connected({e.first}, {e.second}));
        if (e.first == path[0])
            reverse(path.begin(), path.end());
        else {
            while (path.back() != e.first) 
                shiftRight(path);
        }
    } else
        e = getEdge({path.back()}, clique);

    path.push_back(e.second);
    for (int v: clique) {
        if (v == e.second)
            continue;

        // assert(are_connected({path.back()}, {v}));
        path.push_back(v);
    }

    // assert((int)path.size() == n);
    // check(path);
    return path;
}

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