Submission #1232260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232260		LucaIlie	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	96 ms	616 KiB

longesttrip

#include "longesttrip.h"
#include <queue>
#include <stdio.h>

using namespace std;

const int MAX_N = 256;
int n;
bool inComp[MAX_N];
vector<int> adj[MAX_N];

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, c))
            return getEdge(a, c);
        return getEdge(a, d);
    }

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

vector<int> longest_trip(int N, int D) {
    n = N;
    for (int v = 0; v < n; v++)
        inComp[v] = false;

    vector<int> path(1, 0);
    inComp[0] = true;
    for (int i = 1; i < n; i++) {
        vector<int> comp, other;
        for (int v = 0; v < n; v++) {
            if (!inComp[v])
                other.push_back(v);
        }
        comp.push_back(path.back());
        if ((int)path.size() > 1)
            comp.push_back(path[0]);
        for (int i = 1; i < (int)path.size() - 1; i++) 
            comp.push_back(path[i]);

        if (!are_connected(comp, other)) {
            if (comp.size() > other.size())
                return comp;
            return other;
        }

        pair<int, int> e = getEdge(comp, other);
        inComp[e.second] = true;

        int pos = 0;
        while (path[pos] != e.first)
            pos++;

        vector<int> newPath(1, e.second);
        for (int j = pos; j < (int)path.size(); j++)
            newPath.push_back(path[j]);
        for (int j = 0; j < pos; j++)
            newPath.push_back(path[j]);
        path = newPath;
    }

    return path;
}

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