#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 256, T = 1e3;
mt19937 rng(time(nullptr) + (uint64_t) new char);
int cnt;
vector<int> adj[N], ans, curr;
bitset<N> vis, con[N];
void dfs(int u) {
vis[u] = 1;
curr.push_back(u);
cnt++;
if (cnt > T) {
if (curr.size() > ans.size()) ans = curr;
return;
}
//shuffle(all(adj[u]), rng);
for (int& v : adj[u]) {
if (vis[v]) continue;
dfs(v);
if (cnt > T) return;
}
if (curr.size() > ans.size()) ans = curr;
vis[u] = 0;
curr.pop_back();
}
vector<int> longest_trip(int N, int D)
{
if (D == 3) {
ans.resize(N);
for (int i = 0; i < N; i++) ans[i] = i;
return ans;
}
else {
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i);
con[i][j] = con[j][i] = 1;
}
}
}
for (int i = 0; i < 2; i++) {
cnt = 0;
vis.reset();
curr.clear();
for (int j = 0; j < N; j++) {
shuffle(all(adj[j]), rng);
}
dfs(rng() % N);
}
curr.clear();
curr.resize(N);
for (int i = 0; i < n; i++) {
curr[i] = i;
}
for (int i = 0; i < T; i++) {
shuffle(all(curr), rng);
int r = 0;
for (int j = 0; j+1 < n; j++) {
if (con[curr[j]][curr[j+1]]) r++;
else break;
}
if (r+1 > ans.size()) {
ans.clear();
ans.resize(r+1);
for (int j = 0; j <= r; j++) {
ans[j] = curr[j];
}
}
}
return ans;
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:70:29: error: 'n' was not declared in this scope
70 | for (int i = 0; i < n; i++) {
| ^
longesttrip.cpp:77:33: error: 'n' was not declared in this scope
77 | for (int j = 0; j+1 < n; j++) {
| ^
longesttrip.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if (r+1 > ans.size()) {
| ~~~~^~~~~~~~~~~~
