Submission #1244560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244560		trimkus	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	336 ms	672 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;
    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);
        }
    }
    while (dq2.size()) {
        int v = dq2.front();
        dq2.pop_front();
        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 (int j = 0; j < (int)dq1.size(); ++j) {
                if (adj[dq1[j]][v]) {
                    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;
                    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: 0 / 25
• Subtask 4: 0 / 60