#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
const int N = 200005;
std::vector<int> longest_trip(int n, int D)
{
if(D == 3){
vector<int> v;
for(int i = 0; i < n; ++i) v.pb(i);
return v;
}
if(D == 2){
deque<int> v;
v.pb(0);
int o = -1;
for(int i = 1; i < n; ++i){
bool x = are_connected(vi{0}, vi{i});
if(x){
o = i;
v.pb(i);
break;
}
}
if(o == -1){
vi res;
for(int i = 1; i < n; ++i){
res.pb(i);
}
return res;
}
for(int i = 1; i < n; ++i){
if(o == i) continue;
bool x = are_connected(vi{v[0]}, vi{i});
if(x){
v.push_front(i);
}else v.pb(i);
}
vector<int> res(all(v));
return res;
}
vector<vector<int>> g(n);
vector<vector<bool>> is(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
bool ok = are_connected(vi{i}, vi{j});
if(ok){
is[i][j] = is[j][i] = 1;
g[i].pb(j);
g[j].pb(i);
}
}
}
vector<vector<int>> S;
for(int i = 0; i < n; ++i){
if(g[i].empty()){
vi res;
for(int j = 0; j < n; ++j){
if(j != i) res.pb(j);
}
return res;
}
bool okk = 0;
for(auto &s: S){
bool ok = 1;
for(int x: s){
if(is[x][i] == 0) ok = 0;
}
if(ok == 1){
s.pb(i);
okk = 1;
break;
}
}
if(okk == 0){
S.pb(vi{i});
}
}
if(S.size() == 1) return S;
if(S.size() == 2){
for(int &x: S[0]){
for(int &y: S[1]){
if(is[x][y]){
swap(x, S[0].back());
swap(y, S[1][0]);
vi res;
for(int f: S[0]) res.pb(f);
for(int f: S[1]) res.pb(f);
return res;
}
}
}
if(S[0].size() > S[1].size()) return S[0];
return S[1];
}
int s = S.size();
vector<vector<bool>> si(s, vector<bool>(s));
for(int i = 0; i < s; ++i){
for(int j = i + 1; j < s; ++j){
bool ok = 0;
for(int x: S[i]){
for(int y: S[j]){
if(is[x][y]) ok = 1;
}
}
si[i][j] = si[j][i] = ok;
}
}
deque<int> v;
v.pb(0);
int o = -1;
for(int i = 1; i < s; ++i){
bool x = si[0][i];
if(x){
o = i;
v.pb(i);
break;
}
}
if(o == -1){
assert(false);
}
for(int i = 1; i < s; ++i){
if(o == i) continue;
bool x = si[v[0]][i];
if(x){
v.push_front(i);
}else v.pb(i);
}
vi res;
for(int i = 0; i < S.size(); ++i){
if(i + 1 == S.size()){
for(int x: S[i]) res.pb(x);
}else{
bool ok = 0;
for(int j = (int(S[i].size() == 1 ? 0 : 1)); j < S[i].size(); ++j){
for(int l = 0; l < S[i + 1].size(); ++l){
if(is[S[i][j]][S[i + 1][l]]){
swap(S[i][j], S[i].back());
swap(S[i + 1][l], S[i + 1][0]);
ok = 1;
break;
}
}
if(ok) break;
}
for(int x: S[i]) res.pb(x);
}
}
return res;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:85:28: error: could not convert 'S' from 'vector<std::vector<int>>' to 'vector<int>'
85 | if(S.size() == 1) return S;
| ^
| |
| vector<std::vector<int>>
longesttrip.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i = 0; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:139:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | if(i + 1 == S.size()){
| ~~~~~~^~~~~~~~~~~
longesttrip.cpp:143:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int j = (int(S[i].size() == 1 ? 0 : 1)); j < S[i].size(); ++j){
| ~~^~~~~~~~~~~~~
longesttrip.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int l = 0; l < S[i + 1].size(); ++l){
| ~~^~~~~~~~~~~~~~~~~
