Submission #1258282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258282		onbert	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	5 ms	688 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 260;
int n;
int adj[maxn][maxn];
int qry(int u, int v) {
    int ret = are_connected({u}, {v});
    return adj[u][v] = adj[v][u] = ret;
}

vector<int> longest_trip(int N, int D) {
    n = N;
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) adj[i][j] = -1;
    vector<int> a = {0}, b = {1};
    for (int i=2;i<n;i++) {
        int A = a.back(), B = b.back();
        if (qry(A, i)) a.push_back(i);
        else {
            if (adj[A][B] == 0) b.push_back(i);
            else if (adj[A][B] == -1) {
                if (qry(B, i)) b.push_back(i);
                else {
                    while (b.size()) {
                        a.push_back(b.back());
                        b.pop_back();
                    }
                    b.push_back(i);
                }
            } else assert(false);
        }
    }

    // cout << "test\n";
    // for (int i:a) cout << i << " "; cout << endl;
    // for (int i:b) cout << i << " "; cout << endl;

    if (a.size() < b.size()) swap(a, b);
    if (b.size() == 0 || !are_connected(a, b)) return a;

    int asz = a.size(), bsz = b.size();
    int l = 0, r = asz - 1;
    while (l < r) {
        int mid = (l+r)/2;
        vector<int> temp = {a.back()};
        for (int i=0;i<mid;i++) temp.push_back(a[i]);
        if (are_connected(temp, b)) r = mid;
        else l = mid + 1;
    }
    int A = (l - 1 + asz) % asz;
    l = 0, r = bsz - 1;
    while (l < r) {
        int mid = (l+r)/2;
        vector<int> temp = {b.back()};
        for (int i=0;i<mid;i++) temp.push_back(b[i]);
        if (are_connected(temp, {a[A]})) r = mid;
        else l = mid + 1;
    }
    int B = (l - 1 + bsz) % bsz;

    // cout << "Test " << A << " " << a[A] << " " << B << " " << b[B] << endl;
    // for (int i:a) cout << i << " "; cout << endl;
    // for (int i:b) cout << i << " "; cout << endl;

    vector<int> ans;
    if (A == 0) {
        for (int i=asz-1;i>=0;i--) ans.push_back(a[i]);
    } else {
        for (int i=A+1;i<=A+asz;i++) ans.push_back(a[i % asz]);
    }
    if (B == bsz - 1) {
        for (int i=bsz-1;i>=0;i--) ans.push_back(b[i]);
    } else {
        for (int i=B;i<B+bsz;i++) ans.push_back(b[i % bsz]);
    }
    assert(ans.size() == n);
    return ans;
}

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