Submission #1233065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233065		m5588ohammed	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	13 ms	1436 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n,con[501][501];
bool ask(int i,int j){
    if(con[i][j]!=-1) return con[i][j];
    return con[i][j]=con[j][i]=are_connected({i},{j});
}
vector <int> merge(vector <int> a,vector <int> b){
    for(int j:b) a.push_back(j);
    return a;
}
vector <int> case1(vector <int> a,vector<int> b){
    if(are_connected({a.back()},{b[0]})==1){
        return merge(a,b);
    }
    if(are_connected({a[0]},{b.back()})==1){
        return merge(b,a);
    }
    if(are_connected({a[0]},{b[0]})==1){
        reverse(a.begin(),a.end());
        return merge(a,b);
    }
    if(are_connected({a.back()},{b.back()})==1){
        reverse(a.begin(),a.end());
        return merge(b,a);
    }
    return {};
}
pair <int,int> case2(vector <int> a,vector<int> b){
    int l=0,r=(int)a.size()-1,idx1=0,idx2=0;
    while(l<r){
        int mid=(l+r)/2;
        vector <int> A;
        for(int i=l;i<=mid;i++) A.push_back(a[i]);
        if(are_connected(A,b)==1){
            r=mid;
            idx1=mid;
        }
        else{
            l=mid+1;
            idx1=mid+1;
        }
    }
    l=0,r=(int)b.size()-1;
    while(l<r){
        int mid=(l+r)/2;
        vector <int> B;
        for(int i=l;i<=mid;i++) B.push_back(b[i]);
        if(are_connected({a[idx1]},B)==1){
            r=mid;
            idx2=mid;
        }
        else{
            l=mid+1;
            idx2=mid+1;
        }
    }
    return {idx1,idx2};
}
vector<int> longest_trip(int N, int D)
{
    n=N;
    memset(con,-1,sizeof con);
    vector <int> a={0},b={1};
    for(int i=2;i<n;i++){
        if(con[a.back()][b.back()]!=-1){
            if(con[a.back()][b.back()]==1){
                reverse(b.begin(),b.end());
                a=merge(a,b);
                b={i};
            }
            else{
                if(ask(a.back(),i)==1) a.push_back(i);
                else b.push_back(i);
            }
        }
        else{
            ask(a.back(),i);
            ask(b.back(),i);     
            if(con[a.back()][i]==1) a.push_back(i);
            else if(con[b.back()][i]==1) b.push_back(i);
            else{
                reverse(b.begin(),b.end());
                a=merge(a,b);
                b={i};   
            }
        }
    }
    if(are_connected(a,b)==0){
        if(a.size()>b.size()) return a;
        return b;
    }
    vector <int> A={a.back()},B={b.back()};
    if(a.size()>1) A.push_back(a[0]);
    if(b.size()>1) B.push_back(b[0]);
    if(are_connected(A,B)==1) return case1(a,b);
    auto [idx1,idx2]=case2(a,b);
    vector <int> ans;
    for(int i=idx1+1;i<=idx1+((int)a.size());i++) ans.push_back(a[i%((int)a.size())]);
    for(int i=idx2;i<idx2+((int)b.size());i++) ans.push_back(b[i%((int)b.size())]);
    return ans;
}

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