Submission #1135222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135222		79brue	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	5 ms	416 KiB

longesttrip

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

using namespace std;

typedef long long ll;

bool adj(int x, int y){
    return are_connected(vector<int>(1, x), vector<int>(1, y));
}

void mergeVec(vector<int> &A, vector<int> &B){
    while(!B.empty()) A.push_back(B.back()), B.pop_back();
}

vector<int> sliceVec(vector<int> A, int idx){
    vector<int> ret = A;
    while((int)ret.size()-1 > idx) ret.pop_back();
    return ret;
}

vector<int> longest_trip(int N, int D){
    if(D == 3){
        vector<int> v;
        for(int i=0; i<N; i++){
            v.push_back(i);
        }
        return v;
    }
    if(D == 2){
        list<int> v;
        v.push_back(0);
        if(are_connected(vector<int> (1, 0), vector<int> (1, 1))){
            v.push_back(1);
            if(are_connected(vector<int> (1, 1), vector<int> (1, 2))) v.push_back(2);
            else v.push_front(2);
        }
        else{
            v.push_back(2);
            v.push_back(1);
        }
        for(int i=3; i<N; i++){
            if(are_connected(vector<int> (1, v.front()), vector<int> (1, i))) v.push_front(i);
            else v.push_back(i);
        }

        vector<int> vec;
        while(!v.empty()) vec.push_back(v.front()), v.pop_front();
        return vec;
    }

    vector<int> pathA, pathB;
    if(adj(0, 1)) pathA.push_back(0), pathA.push_back(1);
    else pathA.push_back(0), pathB.push_back(1);

    for(int v=2; v<N; v+=2){
        if(v == N-1){ /// 하나 남은 경우
            bool a = adj(v, pathA.back()), b = pathB.empty() ? 1 : adj(v, pathB.back());
            if(a && b){
                pathA.push_back(v);
                mergeVec(pathA, pathB);
            }
            else if(a) pathA.push_back(v);
            else if(b) pathB.push_back(v);
            else exit(1);
            break;
        }
        int w = v+1;
        if(pathB.empty()){ /// 경로가 하나
            int a = pathA.back();
            bool av = adj(a, v), aw = adj(a, w), vw = adj(v, w);
            if(vw && av) pathA.push_back(v), pathA.push_back(w);
            else if(vw && aw) pathA.push_back(w), pathA.push_back(v);
            else if(vw) pathB.push_back(v), pathB.push_back(w);
            else if(av) pathA.push_back(v), pathB.push_back(w);
            else pathA.push_back(w), pathB.push_back(v);
        }
        else{
            int a = pathA.back(), b = pathB.back();
            if(adj(v, w)){
                if(adj(a, v)){
                    pathA.push_back(v), pathA.push_back(w);
                    if(adj(b, w)) mergeVec(pathA, pathB);
                }
                else{ /// b, v가 인접
                    pathB.push_back(v), pathB.push_back(w);
                    if(adj(a, w)) mergeVec(pathA, pathB);
                }
            }
            else{
                if(adj(a, v) && adj(b, w)) pathA.push_back(v), pathB.push_back(w);
                else pathA.push_back(w), pathB.push_back(v);
            }
        }
    }

    /// 두 path로 축약까지 성공, 여기까지 382
    if(pathA.size() < pathB.size()) swap(pathA, pathB);

    /// 잇는 간선이 없다면...
    if(pathB.empty() || !are_connected(pathA, pathB)) return pathA;

    /// 양끝점 연결 여부 확인
    {
        vector<int> vA = {pathA[0], pathA.back()};
        if((int)pathA.size() == 1) vA.pop_back();
        vector<int> vB = {pathB[0], pathB.back()};
        if((int)pathB.size() == 1) vB.pop_back();

        if(are_connected(vA, vB)){ /// 양끝점 중 연결된 쌍이 있다
            int af = pathA[0], ab = pathA.back(), bf = pathB[0], bb = pathB.back();
            if(adj(af, bf)) reverse(pathA.begin(), pathA.end()), reverse(pathB.begin(), pathB.end());
            else if(adj(af, bb)) reverse(pathA.begin(), pathA.end());
            else if(adj(ab, bf)) reverse(pathB.begin(), pathB.end());
            mergeVec(pathA, pathB);
            return pathA;
        }
    }

    /// 나머지를 사이클로 볼 수 있다.
    int L = 0, R = (int)pathA.size() - 1;
    while(L<R){
        int M = (L+R)/2;
        if(are_connected(sliceVec(pathA, M), pathB)) R=M;
        else L=M+1;
    }

    rotate(pathA.begin(), pathA.begin() + L, pathA.end());
    reverse(pathA.begin(), pathA.end());

    L = 0, R = (int)pathB.size() - 1;
    while(L<R){
        int M = (L+R)/2;
        if(are_connected(vector<int> (1, pathA.back()), sliceVec(pathB, M))) R=M;
        else L=M+1;
    }

    rotate(pathB.begin(), pathB.begin() + L, pathB.end());
    reverse(pathB.begin(), pathB.end());

    mergeVec(pathA, pathB);
    return pathA;
}

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