제출 #1310346

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

longesttrip

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

template<typename T>
using vec = std::vector<T>;
using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    vec<int> nodes(N); for (int i = 0; i < N; i++) nodes[i] = i;
    if (D == 3)
        return nodes;
    if (D == 2) {
        deque<int> path{0, are_connected({0}, {1}) ? 1 : 2};
        nodes.erase(find(nodes.begin(), nodes.end(), path.front()));
        nodes.erase(find(nodes.begin(), nodes.end(), path.back()));
        
        while (!nodes.empty()) {
            auto u = nodes.back(); nodes.pop_back();
            if (are_connected({path.front()}, {u}))
                path.push_front(u);
            else
                path.push_back(u);
        }
        
        return vec<int>(path.begin(), path.end());
    }
    
    
    
    list<int> path[2] = {{0}, {1}};
    nodes.erase(find(nodes.begin(), nodes.end(), path[0].back()));
    nodes.erase(find(nodes.begin(), nodes.end(), path[1].back()));
    while (!nodes.empty()) {
        auto u = nodes.back(); nodes.pop_back();
        if (are_connected({path[0].back()}, {u}))
            path[0].push_back(u);
        else if (are_connected({path[1].back()}, {u}))
            path[1].push_back(u);
        else {
            auto &small = path[0], &large = path[1];
            if (small.size() > large.size()) swap(small, large);
            small.reverse();
            large.splice(large.end(), small);
            path[0] = large;
            path[1] = {u};
        }
    }
    
    return path[0].size() > path[1].size() ? vec<int>(path[0].begin(), path[1].end()) : vec<int>(path[1].begin(), path[1].end());
}

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