Submission #1243758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243758		LeonidCuk	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	5 ms	420 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>vrni(vector<int>&v,int r)
{
    vector<int>temp;
    for(int i=0;i<=r;i++)temp.push_back(v[i]);
    return temp;
}
vector<int> longest_trip(int N, int D)
{
    n=N;
    int k1=0;
    vector<int>v1,v2;
    v1.push_back(0);
    v2.push_back(1);
    for(int i=2;i<n;i++)
    {
        if(k1==0)
        {
            if(are_connected({v1.back()},{i}))
            {
                v1.push_back(i);
            }
            else if(are_connected({v2.back()},{i}))
            {
                v2.push_back(i);
                k1=2;
            }
            else
            {
                while(!v2.empty())
                {
                    v1.push_back(v2.back());
                    v2.pop_back();
                }
                v2.push_back(i);
            }
        }
        else if(k1==2)
        {
            if(are_connected({v1.back()},{i}))
            {
                v1.push_back(i);
                k1=0;
            }
            else
            {
                v2.push_back(i);
            }
        }
    }
    if(!are_connected(v1,v2))
    {
        if(v1.size()>v2.size())return v1;
        return v2;
    }
    if(are_connected({v1.back()},{v2[0]}))
    {
        for(int i=0;i<v2.size();i++)
        {
            v1.push_back(v2[i]);
        }
        return v1;
    }
    else if(are_connected({v1.back()},{v2.back()}))
    {
        for(int i=v2.size()-1;i>=0;i--)
        {
            v1.push_back(v2[i]);
        }
        return v1;
    }
    else if(are_connected({v1[0]},{v2[0]}))
    {
        reverse(v1.begin(),v1.end());
        for(int i=0;i<v2.size();i++)
        {
            v1.push_back(v2[i]);
        }
        return v1;
    }
    else if(are_connected({v1[0]},{v2.back()}))
    {
        reverse(v1.begin(),v1.end());
        for(int i=v2.size()-1;i>=0;i--)
        {
            v1.push_back(v2[i]);
        }
        return v1;
    }
    else
    {
        int l=0,r=v1.size()-1;
        while(r>l)
        {
            int m=(l+r)/2;
            vector<int>temp=vrni(v1,m);
            if(are_connected(temp,v2))r=m;
            else l=m+1;
        }
        int k=l;
        l=0,r=v2.size()-1;
        while(r>l)
        {
            int m=(l+r)/2;
            vector<int>temp=vrni(v2,m);
            if(are_connected(temp,{v1[k]}))r=m;
            else l=m+1;
        }
        vector<int>res;
        int i=(k+1)%v1.size();
        while(i!=k)
        {
            res.push_back(v1[i]);
            i=(i+1)%v1.size();
        }
        res.push_back(v1[k]);
        k=l;
        res.push_back(v2[k]);
        i=(k+1)%v2.size();
        while(i!=k)
        {
            res.push_back(v2[i]);
            i=(i+1)%v2.size();
        }
        return res;
    }
}

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