Submission #1240123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240123		bangan	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	7 ms	432 KiB

longesttrip

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

#define pb push_back
#define ALL(a) a.begin(), a.end()

mt19937_64 rng(41346);

bool check(int v, int u) {
    return are_connected({v}, {u});
}

pair<vector<int>, vector<int>> two_path(int N, int D) {
    deque<int> A, B;
    A = {0};
    B = {1};
    vector<int> all(N-2);
    iota(ALL(all), 2);
    // shuffle(ALL(all), rng);

    bool flg = false;
    for (int x : all) {
        int v = A.back();
        int u = B.back();
        if (check(x, v)) {
            flg = false;
            A.pb(x);
        }
        else if (flg) {
            flg = false;
            B.pb(x);
        }
        else if (check(x, u)) {
            flg = true;
            B.pb(x);
        }
        else {
            flg = false;
            while (!B.empty()) {
                A.pb(B.back());
                B.pop_back();
            }
            B.pb(x);
        }
    }
    vector<int> p, q;
    while (!A.empty()) {
        p.pb(A.back());
        A.pop_back();
    }
    while (!B.empty()) {
        q.pb(B.back());
        B.pop_back();
    }
    return make_pair(p, q);
}

std::vector<int> longest_trip(int N, int D) {
    auto [A, B] = two_path(N, D);
    if (A.size() < B.size()) swap(A, B);
    if (B.empty()) return A;

    {
        int v = A[0], u = A.back();
        int x = B[0], y = B.back();
        if (check(u, x)) {
            for (int p : B) A.pb(p);
            return A;
        }
        if (check(v, x)) {
            reverse(ALL(A));
            for (int p : B) A.pb(p);
            return A;
        }
        if (check(v, y)) {
            reverse(ALL(A));
            reverse(ALL(B));
            for (int p : B) A.pb(p);
            return A;
        }
        if (check(u, y)) {
            reverse(ALL(B));
            for (int p : B) A.pb(p);
            return A;
        }

        // if (v!=u) assert(check(v, u));
        // if (x!=y) assert(check(x, y));
    }

    if (!are_connected(A, B)) return A;

    int j = B.size();
    {
        vector<int> vec = B;
        for (int k=128; 1<=k; k>>=1) {
            if (k < vec.size()) {
                vector<int> save;
                for (int _=0; _<k; _++) {
                    save.pb(vec.back());
                    vec.pop_back();
                }
                reverse(ALL(save));

                if (are_connected(vec, A)) j -= k;
                else for (int p : save) vec.pb(p);
            }
        }
    }
    assert(0<j);
    j--;

    int i = A.size();
    {
        vector<int> vec = A;
        for (int k=128; 1<=k; k>>=1) {
            if (k < vec.size()) {
                vector<int> save;
                for (int _=0; _<k; _++) {
                    save.pb(vec.back());
                    vec.pop_back();
                }
                reverse(ALL(save));
            
                if (are_connected(vec, {B[j]})) i -= k;
                else for (int p : save) vec.pb(p);
            }
        }
    }
    assert(0<i);
    i--;

    vector<int> L{A[i]};
    int k = (i+1) % A.size();
    while (k != i) {
        L.pb(A[k]);
        k = (k+1) % A.size();
    }
    reverse(ALL(L));
    
    vector<int> R{B[j]};
    k = (j+1) % B.size();
    while (k != j) {
        R.pb(B[k]);
        k = (k+1) % B.size();
    }

    for (int p : R) L.pb(p);
    return L;
}

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