Submission #1217683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217683		VMaksimoski008	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	4 ms	408 KiB

longesttrip

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

vector<int> longest_trip(int n, int d) {
    vector<int> ans = { 0 };
    set<int> st;

    for(int i=1; i<n; i++) st.insert(i);

    while(st.size() >= 2) {
        int u = *st.begin(); st.erase(u);
        int v = *st.begin(); st.erase(v);
        if(are_connected({ ans.back() }, { u }))
            ans.push_back(u);
        else
            ans.push_back(v);
        if(ans.back() == u) st.insert(v);
        if(ans.back() == v) st.insert(u);
    }

    if(st.size() == 1) {
        int u = *st.begin();
        if(are_connected({ ans.back() }, { u })) {
            ans.push_back(u);
        } else if(are_connected({ 1 }, { u })) {
            vector<int> ans2 = { u };
            for(int x : ans) ans2.push_back(x);
            ans = ans2;
        } else {
            for(int i=0; i+1<ans.size(); i++) {
                if(are_connected({ ans[i] }, { u}) && are_connected({ u }, { ans[i+1] })) {
                    vector<int> ans2;
                    for(int j=0; j<=i; j++) ans2.push_back(ans[j]);
                    ans2.push_back(u);
                    for(int j=i+1; j<ans.size(); j++) ans2.push_back(ans[j]);
                    ans = ans2;
                }
            }
        }
    }

    return ans;
}

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