Submission #1240009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240009		bangan	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	9 ms	416 KiB

longesttrip

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

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

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};
    for (int x=2; x<N; x++) {
        int v = A.back();
        int u = B.back();
        if (check(x, v)) A.pb(x);
        else if (check(x, u)) B.pb(x);
        else {
            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));
    }

    for (int i=0; i<A.size(); i++) for (int j=0; j<B.size(); j++) if (check(A[i], B[j])) {
        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();
        }
        reverse(ALL(R));

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

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