Submission #1217154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217154		omsincoconut	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	4 ms	420 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);
                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) continue;

                paths.push_back({i-2, i-1});
            }
        } else {
            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[1].begin());
                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].begin());
                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++;
            } 
        }
    }

    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