Submission #1217169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217169		omsincoconut	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	8 ms	416 KiB

longesttrip

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

using namespace std;

const int MAXN = 256;

void append(vector<int> &a, vector<int> &b) {
    for (int i : b) a.push_back(i);
}

vector<int> longest_trip(int N, int D) {
    vector<vector<int>> paths;

    for (int i = 2; i < N;) {
        if (paths.size() == 0) {
            bool b01 = are_connected({0}, {1});
            bool b02 = are_connected({0}, {2});
            bool b12 = are_connected({1}, {2});

            if (b01 && b12) paths.push_back({0, 1, 2});
            else if (b02 && b12) paths.push_back({0, 2, 1});
            else if (b01 && b02) paths.push_back({1, 0 ,2});
            else if (b01) paths.push_back({0, 1}), paths.push_back({2});
            else if (b02) paths.push_back({0, 2}), paths.push_back({1});
            else paths.push_back({1, 2}), paths.push_back({0});
            i++;
        } else if (paths.size() == 1) {
            if (i == N-1) {
                if (are_connected({paths[0].back()}, {i})) paths[0].push_back(i);
                else if (are_connected({paths[0][0]}, {i})) paths[0].insert(paths[0].begin(), i);
                else paths.push_back({i});
                i++;
            } else {
                bool passed = false;
                if (are_connected({paths[0].back()}, {i})) paths[0].push_back(i), passed = true;
                else if (are_connected({paths[0][0]}, {i})) paths[0].insert(paths[0].begin(), i), passed = true;
                i++;
                if (passed) continue;

                if (are_connected({paths[0].back()}, {i})) paths[0].push_back(i), passed = true;
                else if (are_connected({paths[0][0]}, {i})) paths[0].insert(paths[0].begin(), i), passed = true;
                i++;
                if (passed) {
                    if (are_connected({i-2}, {i-1})) paths[0].push_back(i-2);
                    else paths.push_back({i-2});
                    continue;
                }

                paths.push_back({i-2, i-1});
            }
        } else if (paths.size() == 2) {
            if (are_connected({paths[0].back()}, {paths[1].back()})) {
                reverse(paths[1].begin(), paths[1].end());
                append(paths[0], paths[1]);
                paths.pop_back();
            } else if (are_connected({paths[0].back()}, {paths[1][0]})) {
                append(paths[0], paths[1]);
                paths.pop_back();
            } else if (are_connected({paths[0][0]}, {paths[1].back()})) {
                reverse(paths[0].begin(), paths[0].end());
                reverse(paths[1].begin(), paths[1].end());
                append(paths[0], paths[1]);
                paths.pop_back();
            } else if (are_connected({paths[0][0]}, {paths[1][0]})) {
                reverse(paths[0].begin(), paths[1].end());
                append(paths[0], paths[1]);
                paths.pop_back();
            } else if (are_connected({i}, {paths[0].back()})) {
                paths[0].push_back(i);
                i++;
            } else if (are_connected({i}, {paths[0][0]})) {
                paths[0].insert(paths[0].begin(), i);
                i++;
            } else if (are_connected({i}, {paths[1].back()})) {
                paths[1].push_back(i);
                i++;
            } else if (are_connected({i}, {paths[1][0]})) {
                paths[1].insert(paths[1].begin(), i);
                i++;
            }
        }

        assert(paths.size() <= 2);
    }

    int nodes_total = 0;
    for (vector<int> v : paths) nodes_total += v.size();
    assert(nodes_total == N);

    if (paths.size() == 1 || paths[0].size() > paths[1].size()) return paths[0];
    else return paths[1];
}

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