Submission #1232287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232287		LucaIlie	가장 긴 여행 (IOI23_longesttrip)	C++17	15 / 100	5 ms	404 KiB

longesttrip

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

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

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

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;
    vector<int> clique;
    for (int i = 1; i < n; i++) {
        if (!are_connected({path.back()}, {i})) {
            clique.push_back(i);
            continue;
        }

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

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

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

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

    pair<int, int> e = getEdge(path, clique);
    assert(are_connected({e.first}, {e.second}));
    while (path.back() != e.first) 
        shiftRight(path);
    for (int v: clique) {
        assert(are_connected({path.back()}, {v}));
        path.push_back(v);
    }

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

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