Submission #1242565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242565		MrAndria	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	8 ms	696 KiB

longesttrip

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

// #include "longesttrip.h"

// #include <cassert>
// #include <cstdio>
// #include <string>
// #include <vector>

// static inline constexpr int maxNumberOfCalls = 32640;
// static inline constexpr int maxTotalNumberOfCalls = 150000;
// static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
// static int call_counter = 0;
// static int total_call_counter = 0;
// static int landmark_counter = 0;

// static int C, N, D;
// static std::vector<std::vector<int>> U;
// static std::vector<bool> present;

// static inline void protocol_violation(std::string message)
// {
//     printf("Protocol Violation: %s\n", message.c_str());
//     exit(0);
// }

// bool are_connected(std::vector<int> A, std::vector<int> B)
// {
//     ++call_counter;
//     ++total_call_counter;
//     if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
//     {
//         protocol_violation("too many calls");
//     }

//     int nA = A.size(), nB = B.size();
//     landmark_counter += nA + nB;
//     if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
//     {
//         protocol_violation("too many elements");
//     }

//     if (nA == 0 || nB == 0)
//     {
//         protocol_violation("invalid array");
//     }
//     for (int i = 0; i < nA; ++i)
//     {
//         if (A[i] < 0 || N <= A[i])
//         {
//             protocol_violation("invalid array");
//         }
//         if (present[A[i]])
//         {
//             protocol_violation("invalid array");
//         }
//         present[A[i]] = true;
//     }
//     for (int i = 0; i < nA; ++i)
//     {
//         present[A[i]] = false;
//     }
//     for (int i = 0; i < nB; ++i)
//     {
//         if (B[i] < 0 || N <= B[i])
//         {
//             protocol_violation("invalid array");
//         }
//         if (present[B[i]])
//         {
//             protocol_violation("invalid array");
//         }
//         present[B[i]] = true;
//     }
//     for (int i = 0; i < nB; ++i)
//     {
//         present[B[i]] = false;
//     }

//     for (int i = 0; i < nA; ++i)
//     {
//         for (int j = 0; j < nB; ++j)
//         {
//             if (A[i] == B[j])
//             {
//                 protocol_violation("non-disjoint arrays");
//             }
//         }
//     }

//     for (int i = 0; i < nA; ++i)
//     {
//         for (int j = 0; j < nB; ++j)
//         {
//             if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
//             {
//                 return true;
//             }
//         }
//     }

//     return false;
// }
int c[257][257];
bool re_connected(int x,int y){
    if(c[x][y]!=-1 )return c[x][y];
    if(c[y][x]!=-1)return c[y][x];
    if(x==y)return 0;
    c[x][y]=are_connected({x},{y});
    return c[x][y];
}
std::vector<int> longest_trip(int N, int D){
    vector <int> v5;
    // v5={0,13,1,3,9,2,7,12,14,8,11,15,5,4,6,10};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            c[i][j]=-1;
        }
    }
    for(int i=0;i<N;i++){
        v5.pb(i);
        
    }
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v5.begin(), v5.end(), g);
    vector <int> v1,v2;
    v1.pb(v5[0]);
    v2.pb(v5[1]);
    for(int i=2;i<N;i++){
        if(re_connected(v1.back(),v5[i])){
            v1.pb(v5[i]);
            continue;
        }
        if(!re_connected(v2.back(),v1.back())){
            v2.pb(v5[i]);
            continue;
        }
        reverse(v2.begin(),v2.end());
        for(auto u:v2){
            v1.pb(u);
        }
        v2.clear();
        v2.pb(v5[i]);
    }
    if(v1.size()!=1 and v2.size()!=1){
        if(are_connected({v1[0],v1.back()},{v2[0],v2.back()})){
            // cout<<"YES3"<<endl;
            // for(int i=0;i<v5.size();i++){
            //     cout<<v5[i]<<" ";

            // }
            // cout<<endl;
            // for(int i=0;i<v1.size();i++){
            //     cout<<v1[i]<<" ";

            // }
            // cout<<endl;
            // for(int i=0;i<v2.size();i++){
            //     cout<<v2[i]<<" ";

            // }
            // cout<<endl;
            if(are_connected({v1.back()},{v2[0]})){
                for(auto u:v2){
                    v1.pb(u);

                }
                return v1;
            }else if(are_connected({v1.back()},{v2.back()})){
                reverse(v2.begin(),v2.end());
                for(auto u:v2){
                    v1.pb(u);

                }
                return v1;
            }else if(are_connected({v1[0]},{v2.back()})){
                for(auto u:v1){
                    v2.pb(u);

                }
                return v2;
            }else{
                reverse(v2.begin(),v2.end());
                for(auto u:v1){
                    v2.pb(u);

                }
                return v2;
            }

        }
    }else{
        if(v2.size()<=v1.size()){
            swap(v1,v2);

        }
        if(are_connected({v1.back()},{v2[0],v2.back()})){
            // cout<<"YES2"<<endl;
            // for(int i=0;i<v5.size();i++){
            //     cout<<v5[i]<<" ";

            // }
            // cout<<endl;
            if(are_connected({v1.back()},{v2[0]})){
                for(auto u:v2){
                    v1.pb(u);
                }
                return v1;
            }else{
                v2.pb(v1[0]);
                return v2;
            }
        }
        // return {-1,-1,-1,-1};
    }

    // cout<<"YES1"<<endl;
    // for(int i=0;i<v5.size();i++){
    //     cout<<v5[i]<<" ";

    // }
    // cout<<endl;
    int l,r,ans,mid,ans1;
    l=0;
    r=v1.size()-1;
    ans=-1;
    while(l<=r){
        mid=(l+r)/2;
        vector <int> v3;
        for(int i=0;i<=mid;i++){
            v3.pb(v1[i]);
        }
        if(are_connected(v3,v2)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }

    }

    if(ans==-1){
        if(v1.size()>=v2.size()){
            return v1;
        }else{
            return v2;
        }
    }
    l=0;
    r=v2.size()-1;
    ans1=-1;
    while(l<=r){
        mid=(l+r)/2;
        vector <int> v3;
        for(int i=0;i<=mid;i++){
            v3.pb(v2[i]);
        }
        if(are_connected({v1[ans]},v3)){
            ans1=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }

    }
    if(ans1<0){
        assert(0);
    }
    vector <int> v;
    for(int i=ans+1;i<v1.size();i++){
        v.pb(v1[i]);
    }
    for(int i=0;i<=ans;i++){
        v.pb(v1[i]);

    }
    for(int i=ans1;i<v2.size();i++){
        v.pb(v2[i]);
    }
    for(int i=0;i<ans1;i++){
        v.pb(v2[i]);
    }
    return v;

}
// int main()
// {
//     assert(1 == scanf("%d", &C));
//     int maximumCalls = 0;
//     for (int c = 0; c < C; ++c)
//     {
//         call_counter = 0;
//         assert(2 == scanf("%d %d", &N, &D));

//         present.assign(N, false);
//         U.resize(N);
//         for (int i = 1; i < N; ++i)
//         {
//             U[i].resize(i);
//             for (int j = 0; j < i; ++j)
//             {
//                 assert(1 == scanf("%d", &U[i][j]));
//             }
//         }

//         for (int i = 2; i < N; ++i)
//         {
//             for (int j = 1; j < i; ++j)
//             {
//                 for (int k = 0; k < j; ++k)
//                 {
//                     if (U[i][j] + U[i][k] + U[j][k] < D)
//                     {
//                         printf("Insufficient Density\n");
//                         exit(0);
//                     }
//                 }
//             }
//         }

//         std::vector<int> t = longest_trip(N, D);
//         int l = t.size();
//         printf("%d\n", l);
//         if(l!=16){
//             cout<<"YESSSSSSSS"<<endl;
//             assert(0);
//         }
//         for (int i = 0; i < l; ++i)
//         {

//             printf(i == 0 ? "%d" : " %d", t[i]);
//         }
//         bool b1=0;
//         cout<<endl;
//         for(int i=0;i<l-1;i++){
//             if(U[max(t[i],t[i+1])][min(t[i],t[i+1])]==0){
//                 cout<<t[i]<<" "<<t[i+1]<<endl;
//                 cout<<"YESSSSSSSSSSSSSSSSSS"<<" "<<c<<endl;
//                 b1=1;
//                 break;
//             }
//         }
//         if(b1)break;
//         printf("\n");
//         printf("%d\n", call_counter);

//         maximumCalls = std::max(maximumCalls, call_counter);
//         call_counter = 0;
//     }
//     printf("%d\n", maximumCalls);

//     return 0;
// }

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