Submission #1086389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086389		qwerasdfzxcl	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	13 ms	968 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int adj[256][256], n;

int E(int x, int y){
    assert(x != y);
    if (adj[x][y] != -1) return adj[x][y];
    adj[x][y] = adj[y][x] = are_connected({x}, {y});

    for (int z=0;z<n;z++) if (x!=z && y!=z){
        if (!adj[x][y] && !adj[x][z]) adj[y][z] = adj[z][y] = 1;
        if (!adj[x][y] && !adj[y][z]) adj[x][z] = adj[z][x] = 1;
    }

    return adj[x][y];
}

vector<int> rev(vector<int> A){
    reverse(A.begin(), A.end());
    return A;
}

vector<int> operator + (const vector<int> &A, const vector<int> &B){
    vector<int> ret = A;
    for (auto &x:B) ret.push_back(x);
    return ret;
}


std::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;
    for (int i=0;i<N;i++) adj[i][i] = 0;

    vector<int> A = {0}, B, fuck;
    mt19937 seed(1557);
    for (int i=1;i<N;i++) fuck.push_back(i);
    shuffle(fuck.begin(), fuck.end(), seed);
    for (int i:fuck){
        if (B.empty()) {B.push_back(i); continue;}
        if (E(A.back(), i)) {A.push_back(i); continue;}
        if (E(B.back(), i)) {B.push_back(i); continue;}
        
        A = A + rev(B);

        B.clear();
        B.push_back(i);
    }

    if (!are_connected(A, B)){
        if (A.size() >= B.size()) return A;
        return B;
    }

    if (E(A.back(), B[0])) return A + B;
    if (E(A.back(), B.back())) return A + rev(B);
    if (E(A[0], B.back())) return rev(A) + rev(B);
    if (E(A[0], B[0])) return rev(A) + B;

    int l = 0, r = (int)A.size()-1, ans1 = (int)A.size()-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if (are_connected(vector<int>(A.begin(), A.begin()+mid+1), B)) ans1 = mid, r = mid-1;
        else l = mid+1;
    }

    l = 0, r = (int)B.size()-1;
    int ans2 = (int)B.size()-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if (are_connected({A[ans1]}, vector<int>(B.begin(), B.begin()+mid+1))) ans2 = mid, r = mid-1;
        else l = mid+1;
    }

    rotate(A.begin(), A.begin()+ans1, A.end());
    rotate(B.begin(), B.begin()+ans2, B.end());
    return rev(A) + B;
}

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