Submission #1070335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070335		Plurm	Longest Trip (IOI23_longesttrip)	C++17	25 / 100	14 ms	612 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N, int D) {
    vector<vector<int>> g(N);
    vector<deque<int>> comp(N);
    for (int i = 0; i < N; i++)
        comp[i].push_back(i);
    while (comp.size() > 2) {
        int i = 0;
        int j = 1;
        int k = 2;
        int u = comp[i].back();
        int v = comp[j].back();
        int w = comp[k].back();
        if (are_connected({v}, {w})) {
            swap(u, w);
            swap(i, k);
        } else if (are_connected({u}, {w})) {
            swap(v, w);
            swap(j, k);
        }
        g[u].push_back(v);
        g[v].push_back(u);
        reverse(comp[j].begin(), comp[j].end());
        comp[i].insert(comp[i].end(), comp[j].begin(), comp[j].end());
        comp.erase(comp.begin() + j);
    }
    if (comp[0].size() < comp[1].size()) {
        swap(comp[0], comp[1]);
    }
    return vector<int>(comp[0].begin(), comp[0].end());
}

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