제출 #1305167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305167		nathlol2	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	8 ms	432 KiB

longesttrip

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

std::vector<int> longest_trip(int N, int D){
    vector<int> ans;
    if(D == 3){
        ans.resize(N);
        iota(ans.begin(), ans.end(), 0);
        return ans;
    }else if(D == 2){
        int pa[N], h1 = 0, h2 = 1;
        for(int i = 0;i<N;i++) pa[i] = -1;
        if(are_connected({0}, {1})){
            pa[1] = 0;
            for(int i = 2;i<N;i++){
                if(are_connected({i}, {h1})){
                    pa[i] = h1;
                    h1 = i;
                }else{
                    pa[i] = h2;
                    h2 = i;
                }
            }
            int id = h1;
            while(id != 0){
                ans.push_back(id);
                id = pa[id];
            }
            ans.push_back(0);
            vector<int> tmp;
            id = h2;
            while(id != 0){
                tmp.push_back(id);
                id = pa[id];
            }
            reverse(tmp.begin(), tmp.end());
            for(auto x : tmp){
                ans.push_back(x);
            }
            return ans;
        }else{
            pa[0] = 2;
            pa[1] = 2;
            for(int i = 3;i<N;i++){
                if(are_connected({i}, {h1})){
                    pa[i] = h1;
                    h1 = i;
                }else{
                    pa[i] = h2;
                    h2 = i;
                }
            }
            int id = h1;
            while(id != 2){
                ans.push_back(id);
                id = pa[id];
            }
            ans.push_back(2);
            vector<int> tmp;
            id = h2;
            while(id != 2){
                tmp.push_back(id);
                id = pa[id];
            }
            reverse(tmp.begin(), tmp.end());
            for(auto x : tmp){
                ans.push_back(x);
            }
            return ans;
        }
    }else{
        vector<vector<int>> adj(N);
        int h1 = 0, t1 = 0, h2 = 1, t2 = 1, lucky = 0;
        for(int i = 2;i<N;i++){
            if(lucky){
                if(lucky == 1){
                    if(are_connected({i}, {t1})){
                        adj[i].push_back(t1);
                        adj[t1].push_back(i);
                        t1 = i;
                    }else{
                        adj[i].push_back(t2);
                        adj[t2].push_back(i);
                        t2 = i;
                    }
                }else{
                    if(are_connected({i}, {t2})){
                        adj[i].push_back(t2);
                        adj[t2].push_back(i);
                        t2 = i;
                    }else{
                        adj[i].push_back(t1);
                        adj[t1].push_back(i);
                        t1 = i;
                    }
                }
                lucky = 0;
            }else{
                if(are_connected({i}, {t1})){
                    adj[i].push_back(t1);
                    adj[t1].push_back(i);
                    t1 = i;
                    lucky = 0;
                }else if(are_connected({i}, {t2})){
                    adj[i].push_back(t2);
                    adj[t2].push_back(i);
                    t2 = i;
                    lucky = 1;
                }else{
                    adj[t1].push_back(t2);
                    adj[t2].push_back(t1);
                    t1 = h2;
                    h2 = i;
                    t2 = i;
                    lucky = 2;
                }
            }
        }
        vector<int> l1, l2;
        int id = h1, pv = -1;
        while(id != t1){
            l1.push_back(id);
            int nxt = id;
            for(auto v : adj[id]){
                if(v != pv){
                    nxt = v;
                }
            }
            pv = id;
            id = nxt;
        }
        l1.push_back(t1);
        id = h2, pv = -1;
        while(id != t2){
            l2.push_back(id);
            int nxt = id;
            for(auto v : adj[id]){
                if(v != pv){
                    nxt = v;
                }
            }
            pv = id;
            id = nxt;
        }
        l2.push_back(t2);
        if(are_connected(l1, l2)){
            vector<int> ask1, ask2;
            ask1.push_back(l1[0]);
            if(l1.size() != 1) ask1.push_back(l1[l1.size() - 1]);
            ask2.push_back(l2[0]);
            if(l2.size() != 1) ask2.push_back(l2[l2.size() - 1]);
            if(are_connected(ask1, ask2)){
                if(are_connected({l1[0]}, {l2[0]})){
                    reverse(l1.begin(), l1.end());
                    for(auto x : l1) ans.push_back(x);
                    for(auto x : l2) ans.push_back(x);
                    return ans;
                }else if(are_connected({l1[0]}, {l2[l2.size() - 1]})){
                    ans = l2;
                    for(auto x : l1) ans.push_back(x);
                    return ans;
                }else if(are_connected({l1[l1.size() - 1]}, {l2[0]})){
                    ans = l1;
                    for(auto x : l2) ans.push_back(x);
                    return ans;
                }else{
                    ans = l1;
                    reverse(l2.begin(), l2.end());
                    for(auto x : l2) ans.push_back(x);
                    return ans;
                }
            }
            int l = 0, r = l1.size() - 1, ans1 = -1, ans2 = -1;
            while(l <= r){
                int md = (l + r) / 2;
                vector<int> tmp;
                for(int i = 0;i<=md;i++) tmp.push_back(l1[i]);
                if(are_connected(tmp, l2)){
                    ans1 = md;
                    r = md - 1;
                }else{
                    l = md + 1;
                }
            }
            l = 0, r = l2.size() - 1;
            while(l <= r){
                int md = (l + r) / 2;
                vector<int> tmp;
                for(int i = 0;i<=md;i++) tmp.push_back(l2[i]);
                if(are_connected({l1[ans1]}, tmp)){
                    ans2 = md;
                    r = md - 1;
                }else{
                    l = md + 1;
                }
            }
            for(int i = ans1 + 1;i<l1.size();i++){
                ans.push_back(l1[i]);
            }
            for(int i = 0;i<=ans1;i++){
                ans.push_back(l1[i]);
            }
            for(int i = ans2;i<l2.size();i++){
                ans.push_back(l2[i]);
            }
            for(int i = 0;i<ans2;i++){
                ans.push_back(l2[i]);
            }
            return ans;
        }else{
            if(l1.size() >= l2.size()){
                return l1;
            }else{
                return l2;
            }
        }
    }
}

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