Submission #979252

#	Time	Username	Problem	Language	Result	Execution time	Memory
979252		ALeonidou	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	14 ms	688 KiB

longesttrip

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

using namespace std;

#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define endl "\n"
#define pb push_back

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(const vi &v){
    for (ll i =0; i<sz(v); i++)
        cout<<v[i]<<" ";
    cout<<endl;
}

vi longest_trip(int n, int d){
    vi st1, st2;
    st1.pb(0);
    st2.pb(1);

    //create stacks
    for (ll i = 2; i<n; i++){
        ll x = are_connected({st1.back()}, {i});
        ll y = are_connected({st2.back()}, {i});
        if (x){
            st1.pb(i);
        }
        else if (y){
            st2.pb(i);
        }
        else{
            for (ll j = 0; j<sz(st1); j++){
                st2.pb(st1[j]);
            }
            st1.assign(1, i);
        }
    }

    // cout<<"st1: ";
    // printVct(st1);
    // cout<<"st2: ";
    // printVct(st2);

    //merge stacks if possible  
    if (are_connected({st1[0]}, {st2.back()})){
        vi ans;
        for (ll i = 0; i<sz(st2); i++) ans.pb(st2[i]);
        for (ll i = 0; i<sz(st1); i++) ans.pb(st1[i]);
        return ans;
    }
    else if (are_connected({st1.back()}, {st2[0]})){
        vi ans;
        for (ll i = 0; i<sz(st1); i++) ans.pb(st1[i]);
        for (ll i = 0; i<sz(st2); i++) ans.pb(st2[i]);
        return ans;
    }
    else if (are_connected({st1[0]}, {st2[0]})){
        vi ans;
        for (ll i = sz(st1)-1; i>=0; i--) ans.pb(st1[i]);
        for (ll i = 0; i<sz(st2); i++) ans.pb(st2[i]);
        return ans;
    }
    else if (are_connected({st1.back()}, {st2.back()})){
        vi ans;
        for (ll i = 0; i<sz(st1); i++) ans.pb(st1[i]);
        for (ll i = sz(st2)-1; i>=0; i--) ans.pb(st2[i]);
        return ans;
    }


    // cout<<"CHECK 0"<<endl;

    //search for first connnection between stacks
    ll firstConnectionStart = 1;
    while ((firstConnectionStart < sz(st1)-1) && !are_connected({st1[firstConnectionStart]}, st2)){
        firstConnectionStart++;
    }
    // dbg(firstConnectionStart);

    if (firstConnectionStart >= sz(st1) - 1){   //no connection case => 2 strongly/fully connected stacks
        // cout<<"CHECK 2"<<endl;
        if (sz(st1) > sz(st2)){
            return st1;
        }
        else{
            return st2;
        }
    }

    ll firstConnectionEnd = 1;
    while (!are_connected({st2[firstConnectionEnd]}, {firstConnectionStart})){
        firstConnectionEnd++;
    }
    // dbg(firstConnectionEnd);

    // cout<<"CHECK 1"<<endl;
    // return vi();

    vi ans;
    for (ll i = firstConnectionStart+1; i<sz(st1); i++){
        ans.pb(st1[i]);
    }
    for (ll i = 0; i<=firstConnectionStart; i++){
        ans.pb(st1[i]);
    }
    for (ll i = firstConnectionEnd; i<sz(st2); i++){
        ans.pb(st2[i]);
    }
    for (ll i =0; i<firstConnectionEnd; i++){
        ans.pb(st2[i]);
    }
    return ans;
}

/*
2
5 1
1
1 1
0 0 1
0 0 0 1
4 1
1
0 0
0 0 1


5
1 0 2 3 4
4
2
0 1
3
4

1
3 1
0
0 1

1
3 1
1
0 0

*/

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