제출 #1201255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201255		PagodePaiva	가장 긴 여행 (IOI23_longesttrip)	C++20	60 / 100	104 ms	464 KiB

longesttrip

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

using namespace std;

const int N = 260;
int mark[N];
vector <int> usados;
set <int> s;

vector<int> longest_trip(int N, int D){
    for(int i = 0;i < N;i++){
        mark[i] = 0;
    }
    usados.clear();
    s.clear();
    deque <int> ans;
    ans.push_back(0);
    usados.push_back(0);
    mark[0] = 1;
    for(int i = 1;i < N;i++){
        if(are_connected({0}, {i})){
            ans.push_back(i);
            usados.push_back(i);
            mark[i] = 1;
            break;
        }
    }
    for(int i = 1;i < N;i++){
        if(mark[i])
            continue;
        s.insert(i);
    }
    bool aux = true;
    while(!s.empty()){        
        int i = (*s.begin());
        if(aux){
            vector <int> nao_usados;
            for(auto x : s){
                if(mark[i])
                    continue;
                nao_usados.push_back(x);
            }
            if(!are_connected(usados, nao_usados)){
                if(usados.size() < nao_usados.size()) swap(usados, nao_usados);
                return usados;
            }
            else{
                int l = 0, r = nao_usados.size();
                r--;
                while(l < r){
                    int mid = (l+r)/2;
                    vector <int> v;
                    for(int i = l;i <= mid;i++){
                        v.push_back(nao_usados[i]);
                    }
                    if(are_connected(v, usados)){
                        r = mid;
                    }
                    else{
                        l = mid+1;
                    }
                }
                int x = nao_usados[l];
                l = 0, r = usados.size();
                r--;
                while(l < r){
                    int mid = (l+r)/2;
                    vector <int> v;
                    for(int i = l;i <= mid;i++){
                        v.push_back(usados[i]);
                    }
                    if(are_connected({x}, v)){
                        r = mid;
                    }
                    else{
                        l = mid+1;
                    }
                }
                //cout << usados[l] << '\n';
                while(ans.back() != usados[l]){
                    int y = ans.back();
                    ans.pop_back();
                    ans.push_front(y);
                }
                ans.push_back(x);
                usados.push_back(x);
                s.erase(x);
            }
            if(!are_connected({ans.front()}, {ans.back()}))
                aux = false;
        }
        else{
            int x = ans.front(), y = ans.back();
            bool a = are_connected({i}, {x}), b = are_connected({i}, {y});
            if(a and b){
                aux = true;
                ans.push_back(i);
            }
            else if(a){
                ans.push_front(i);
            }
            else if(b){
                ans.push_back(i);
            }
            usados.push_back(i);
            s.erase(i);
        }
    }
    vector <int> resposta;
    while(!ans.empty()){
        resposta.push_back(ans.front());
        ans.pop_front();
    }
    return resposta;
}

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