#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second map<vector<int>, map<vector<int>, int> > mmm; int query(vector<int> a, vector<int> b){ if (!mmm[a][b]&&!mmm[b][a])mmm[b][a]=mmm[a][b]=are_connected(a, b)+1; return mmm[a][b]-1; } vector<int> longest_trip(int n, int d){ mmm.clear(); if (d==3){ vector<int> ans; for (int i=0; i<n; ++i)ans.pb(i); return ans; } if (d==2){ deque<int> ans(1, 0); int done=1; if (are_connected({0}, {1}))ans.pb(1); else ans.pb(2), done=2; for (int i=1; i<n; ++i)if (i!=done){ if (are_connected({i}, {ans.back()}))ans.pb(i); else ans.push_front(i); } vector<int> res; for (auto a:ans)res.pb(a); return res; } int aa=-1, bb=-1, cc=-1; for (int i=0; i<n; ++i){ int ooga=-1; for (int j=0; j<n; ++j){ if (ooga==-1&&i!=j&&query({i}, {j}))ooga=j; else if (ooga!=-1&&i!=j&&query({i}, {j})){ aa=i, bb=ooga, cc=j; break; } } } deque<int> a(1, bb), b; bool first=1; for (int i=0; i<n; ++i){ if (i!=aa&&i!=bb&&i!=cc&&!first){ if (query({i}, {a.back()}))a.pb(i); else if (query({i}, {b.back()}))b.pb(i); else{ while (b.size())a.pb(b.back()), b.pop_back(); b.pb(i); } } else if (i!=aa&&i!=bb&&i!=cc&&first)b.pb(i); } if (query({cc}, {a.back()}))a.pb(cc); else if (b.size()&&query({cc}, {b.back()}))b.pb(cc); else{ while (b.size())a.pb(b.back()), b.pop_back(); b.pb(cc); } if (b.size()>a.size())swap(a, b); if (b.empty()){ vector<int> res; for (auto c:a)res.pb(c); return res; } if (query({a.back()}, {b.back()})){ while (b.size())a.pb(b.back()), b.pop_back(); } else if (query({a.back()}, {b[0]})){ for (auto c:b)a.pb(c); } else if (query({a[0]}, {b.back()})){ while (b.size())a.push_front(b.back()), b.pop_back(); } else if (query({a[0]}, {b[0]})){ for (auto c:b)a.push_front(c); } else{ for (int i=1; i<b.size()-1; ++i)if (query({b[i]}, {a[0], a.back()})){ if (query({b[i]}, {a.back()}))for (int j=0; j<b.size(); ++j)a.pb(b[(i+j)%b.size()]); else for (int j=0; j<b.size(); ++j)a.push_front(b[(i+j)%b.size()]); } } vector<int> res; for (auto c:a)res.pb(c); return res; }