제출 #1244574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244574		trimkus	가장 긴 여행 (IOI23_longesttrip)	C++20	40 / 100	334 ms	676 KiB

longesttrip

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

using namespace std;
int N;
const int MAXN = 256;
int adj[MAXN][MAXN];



std::vector<int> longest_trip(int _N, int D)
{
    N = _N;
    // cerr << N << "\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            adj[i][j] = 0;
        }
    }
    for (int i = 0; i < N; ++i) {
        adj[i][i] = 1;
        for (int j = i + 1; j < N; ++j) {
            if (are_connected({i}, {j})) {
                adj[i][j] = 1;
                adj[j][i] = 1;
            }
        }
    }
    if (N <= 5) {
        vector<int> res, ord(N);
        iota(begin(ord), end(ord), 0);
        do {
            vector<int> now{ord[0]};
            for (int j = 1; j < N; ++j) {
                if (!adj[ord[j - 1]][ord[j]]) {
                    break;
                }
                now.push_back(ord[j]);
            }
            if (res.size() < now.size()) res = now;
        } while (next_permutation(begin(ord), end(ord)));
        return res;
    }
    deque<int> dq1, dq2;
    dq1.push_back({0});
    for (int i = 1; i < N; ++i) {
        if (adj[dq1.front()][i]) {
            dq1.push_front(i);
        } else if (adj[dq1.back()][i]){
            dq1.push_back(i);
        } else {
            dq2.push_back(i);
        }
    }
    if (dq1.size() < dq2.size()) swap(dq1, dq2);
    // for (auto& u : dq1) {
    //     cout << u << " ";
    // }
    // cout << "\n";
    // for (auto& u : dq2) {
    //     cout << u << " ";
    // }
    // cout << "\n";
    while (dq2.size()) {
        int v = dq2.front();
        dq2.pop_front();
        // cout << v << "\n";
        if (adj[dq1.front()][v]) {
            dq1.push_front(v);
        } else if (adj[dq1.back()][v]) {
            dq1.push_back(v);
        } else {
            assert(adj[dq1.front()][dq1.back()]);
            // for (auto& u : dq1) {
            //     cout << u << " ";
            // }
            // cout << "\n";
            for (int j = 0; j < (int)dq1.size(); ++j) {
                if (adj[dq1[j]][v]) {
                    // cout << j << " => ";
                    deque<int> nw;
                    for (int k = 0; k <= j; ++k) {
                        nw.push_back(dq1[k]);
                    }
                    for (int k = dq1.size() - 1; k > j; --k) {
                        nw.push_front(dq1[k]);
                    }
                    nw.push_back(v);
                    dq1 = nw;
                    // for (auto& u : dq1) {
                    //     cout << u << " ";
                    // }
                    // cout << "\n";
                    break;
                }
            }
        }
    }
    vector<int> res;
    while (dq1.size()) {
        res.push_back(dq1.front());
        dq1.pop_front();
    }
    // cerr << res.size() << "\n";
    return res;
}

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