#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
int binary_search(vector <int> & path, int v){
int l = -1, r = (int)path.size()-1;
while (r-l > 1){
int m = (l + r) / 2;
vector <int> cur(m+1);
for (int i = 0; i <= m; i++) cur[i] = path[i];
if (are_connected(cur, {v})) r = m;
else l = m;
}
return r;
}
vector <int> longest_trip(int N, int D){
vector <int> path, clique, used(N);
for (int i = 0; i <= 2; i++){
for (int j = 0; j < i; j++){
if (are_connected({i}, {j})){
path = {i, j};
used[i] = used[j] = 1;
break;
}
}
if (!path.empty()) break;
}
vector <int> non_edge;
mt1993777 rnd(239);
for (int v = 0; v < N; v++){
if (used[v]) continue;
if (rnd() % 2) reverse(path.begin(), path.end());
int P = path.size();
int C = clique.size();
int st = path[0], fin = path[P-1];
// cout << v << endl;
// for (int x : path) cout << x << " ";
// cout << endl;
// for (int y : clique) cout << y << endl;
// cout << endl;
if (!clique.empty()){
int cp = are_connected(path, {v});
int cc = are_connected(clique, {v});
if (cp && cc){
non_edge = {clique[0], path[0]};
int ip = binary_search(path, v);
int ic = binary_search(clique, v);
vector <int> npath;
for (int j = 0; j < P; j++) npath.push_back(path[(j+ip+1)%P]);
npath.push_back(v);
for (int j = 0; j < C; j++) npath.push_back(clique[(j+ic)%C]);
path = npath;
clique.clear();
continue;
}
else if (cc){
clique.push_back(v);
continue;
}
else if (cp){
path.push_back(v);
continue;
}
}
if (!non_edge.empty()){
if (are_connected({st}, {fin})){
int u = (are_connected({non_edge[0]}, {v}) ? non_edge[0] : non_edge[1]);
int i = -1;
for (int ii = 0; ii < P; ii++)
if (path[ii] == u) i = ii;
vector <int> npath;
for (int j = 0; j < P; j++)
npath.push_back(path[(j+i+1)%P]);
npath.push_back(v);
path = npath;
continue;
}
else{
if (are_connected({st}, {v})){
reverse(path.begin(), path.end());
path.push_back(v);
continue;
}
else{
path.push_back(v);
continue;
}
}
}
if (are_connected({st}, {v})){
reverse(path.begin(), path.end());
path.push_back(v);
continue;
}
if (!are_connected(path, {v})){
clique.push_back(v);
continue;
}
if (non_edge.empty()) non_edge = {st, v};
if (are_connected({fin}, {v})){
path.push_back(v);
continue;
}
int i = binary_search(path, v);
vector <int> npath;
for (int j = 0; j < P; j++)
npath.push_back(path[(j+i+1)%P]);
npath.push_back(v);
path = npath;
}
assert(path.size() + clique.size() == N);
if (path.size() >= clique.size()) return path;
else return clique;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:31:5: error: 'mt1993777' was not declared in this scope
31 | mt1993777 rnd(239);
| ^~~~~~~~~
longesttrip.cpp:35:13: error: 'rnd' was not declared in this scope; did you mean 'rand'?
35 | if (rnd() % 2) reverse(path.begin(), path.end());
| ^~~
| rand
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from longesttrip.cpp:1:
longesttrip.cpp:125:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
125 | assert(path.size() + clique.size() == N);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
