Submission #1187777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187777		MatteoArcari	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	1101 ms	525856 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

bool are_connected(vector<int> A, vector<int> B);

vector<int> connect(vector<int> a, vector<int> b) {
    reverse(b.begin(), b.end());
    for (auto x: b) a.push_back(x);
    return a;
}

vector<int> connect_cycles(vector<int> a, int _i, vector<int> b, int _j) {
    vector<int> res;
    for (int i = (_i + 1) % a.size(); i != _i; i = (i + 1) % a.size()) {
        res.push_back(a[i]);
    }
    for (int i = _j; (i + 1) % b.size() != _j; i = (i + 1) % b.size()) {
        res.push_back(b[i]);
    }
    return res;
}

vector<int> longest_trip(int n, int d) {
    vector<int> pathA = {0}, pathB = {1};

    for (int i = 2; i < n; i++) {
        if (are_connected({pathA.back()}, {i})) {
            pathA.push_back(i);
        } else if (are_connected({pathB.back()}, {i})) {
            pathB.push_back(i);
        } else {
            pathA = connect(pathA, pathB);
            pathB = {i};
        }
    }

    if (pathA.size() < pathB.size()) swap(pathA, pathB);

    if (are_connected(pathA, pathB) == false) return pathA;

    if (are_connected({pathB.back()}, {pathA.back()})) {
        return connect(pathA, pathB);
    }
    reverse(pathA.begin(), pathA.end());
    if (are_connected({pathB.back()}, {pathA.back()})) {
        return connect(pathA, pathB);
    }
    // A è ciclico

    reverse(pathB.begin(), pathB.end());
    if (are_connected({pathB.back()}, {pathA.back()})) {
        return connect(pathA, pathB);
    }

    // B è ciclico

    int i = -1, j = -1;
    for (int k = 1 << 9; k; k >>= 1) {
        if (i + k >= pathA.size()) continue;
        vector<int> check(pathA.begin(), pathA.begin() + i + k + 1);
        if (are_connected(pathB, check) == false) i += k;
    }

    for (int k = 1 << 9; k; k >>= 1) {
        if (j + k >= pathB.size()) continue;
        vector<int> check(pathB.begin(), pathB.begin() + j + k + 1);
        if (are_connected(pathA, check) == false) j += k;
    }
    return connect_cycles(pathA, i, pathB, j);
}

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