#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int mxN = 256;
vector<int> adj[mxN];
vector<int> grp[mxN];
bool con[mxN][mxN];
int n;
int dsupp[mxN];
vector<int> nxt[mxN];
bool vis[mxN];
void resetvis() {
for (int i = 0; i < n; i++) vis[i] = false;
}
void reset() {
for (int i = 0; i < n; i++) {
adj[i].clear();
grp[i].clear();
for (int j = 0; j < n; j++) {
con[i][j] = 0;
}
dsupp[i] = i;
nxt[i].clear();
vis[i] = false;
}
}
int DSUFind(int u) {
if (dsupp[u] == u) return u;
return (dsupp[u] = DSUFind(dsupp[u]));
}
void DSUMerge(int u, int v) {
u = DSUFind(u); v = DSUFind(v);
if (u != v) dsupp[v] = u;
}
vector<int> GetPath(int st) {
resetvis();
vector<int> res;
while (true) {
res.pb(st);
vis[st] = true;
bool found = false;
for (int &v : nxt[st]) {
if (!vis[v]) {
st = v;
found = true;
break;
}
}
if (!found) break;
}
return res;
}
vector<int> MakePath(vector<int> &v) {
if (v.size() == 1) return {v[0]};
if (v.size() == 2) {
if (con[v[0]][v[1]]) return {v[0], v[1]};
else return {v[0]};
}
if (v.size() == 3) {
if (con[v[0]][v[1]] && con[v[0]][v[2]]) return {v[1], v[0], v[2]};
if (con[v[0]][v[1]] && con[v[1]][v[2]]) return {v[0], v[1], v[2]};
if (con[v[0]][v[2]] && con[v[1]][v[2]]) return {v[0], v[2], v[1]};
if (con[v[0]][v[1]]) return {v[0], v[1]};
if (con[v[0]][v[2]]) return {v[0], v[2]};
if (con[v[1]][v[2]]) return {v[1], v[2]};
return {v[0]};
}
for (int i = 0; i < n; i++) {
nxt[i].clear();
}
pair<pii, pii> cur = {{v[0], v[0]}, {v[1], v[1]}};
for (int i = 2; i < (int)(v.size()); i++) {
if (con[cur.ff.ff][cur.ss.ff]) {
nxt[cur.ff.ff].pb(cur.ss.ff);
nxt[cur.ss.ff].pb(cur.ff.ff);
cur.ff.ff = cur.ss.ss;
cur.ss = {v[i], v[i]};
} else if (con[cur.ff.ff][v[i]]) {
nxt[cur.ff.ff].pb(v[i]);
nxt[v[i]].pb(cur.ff.ff);
cur.ff.ff = v[i];
} else if (con[cur.ss.ff][v[i]]) {
nxt[cur.ss.ff].pb(v[i]);
nxt[v[i]].pb(cur.ss.ff);
cur.ss.ff = v[i];
} else throw runtime_error("no connected?");
}
int st;
if (con[cur.ff.ff][cur.ss.ff]) {
nxt[cur.ff.ff].pb(cur.ss.ff);
nxt[cur.ss.ff].pb(cur.ff.ff);
st = cur.ff.ss;
} else if (con[cur.ff.ff][cur.ss.ss]) {
nxt[cur.ff.ff].pb(cur.ss.ss);
nxt[cur.ss.ss].pb(cur.ff.ff);
st = cur.ff.ss;
} else if (con[cur.ff.ss][cur.ss.ff]) {
nxt[cur.ff.ss].pb(cur.ss.ff);
nxt[cur.ss.ff].pb(cur.ff.ss);
st = cur.ff.ff;
} else if (con[cur.ff.ss][cur.ss.ss]) {
nxt[cur.ff.ss].pb(cur.ss.ss);
nxt[cur.ss.ss].pb(cur.ff.ss);
st = cur.ff.ff;
} else {
vector<int> res[2];
res[0] = GetPath(cur.ff.ff);
res[1] = GetPath(cur.ss.ff);
// cerr << "res0: ";
// for (int &x : res[0]) cerr << x << ' ';
// cerr << endl;
// cerr << "res1: ";
// for (int &x : res[1]) cerr << x << ' ';
// cerr << endl;
bool found = false;
for (int i = 0; i < (int)(res[0].size()); i++) {
for (int j = 0; j < (int)(res[1].size()); j++) {
if (con[res[0][i]][res[1][j]]) {
nxt[res[0][i]].pb(res[1][j]);
nxt[res[1][j]].pb(res[0][i]);
if (res[0].size() >= 3) {
nxt[cur.ff.ff].pb(cur.ff.ss);
nxt[cur.ff.ss].pb(cur.ff.ff);
st = (i == 0 ? res[0].back() : res[0][i + 1]);
vector<int>::iterator it;
for (it = nxt[st].begin(); it != nxt[st].end(); ++it) {
if (*it == res[0][i]) {
nxt[st].erase(it);
break;
}
}
for (it = nxt[res[0][i]].begin(); it != nxt[res[0][i]].end(); ++it) {
if (*it == st) {
nxt[res[0][i]].erase(it);
break;
}
}
} else {
st = (res[0].size() == 2 ? res[0][i ^ 1] : res[0][i]);
}
if (res[1].size() >= 3) {
nxt[cur.ss.ff].pb(cur.ss.ss);
nxt[cur.ss.ss].pb(cur.ss.ff);
int tar = (j == 0 ? res[1].back() : res[1][j + 1]);
vector<int>::iterator it;
for (it = nxt[tar].begin(); it != nxt[tar].end(); ++it) {
if (*it == res[1][j]) {
nxt[tar].erase(it);
break;
}
}
for (it = nxt[res[1][j]].begin(); it != nxt[res[1][j]].end(); ++it) {
if (*it == tar) {
nxt[res[1][j]].erase(it);
break;
}
}
}
found = true;
break;
}
}
if (found) break;
}
if (!found) throw runtime_error("oh no");
}
// cerr << "find path for: ";
// for (int &x : v) cerr << x << ' ';
// cerr << endl;
return GetPath(st);
}
vector<int> longest_trip(int N, int D)
{
n = N;
reset();
if (D == 3) {
vector<int> res(n);
for (int i = 0; i < n; i++) res[i] = i;
return res;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (are_connected({i}, {j})) {
adj[i].pb(j);
adj[j].pb(i);
con[i][j] = con[j][i] = true;
DSUMerge(i, j);
}
}
}
for (int i = 0; i < n; i++) {
grp[DSUFind(i)].pb(i);
}
vector<int> best = {};
for (int i = 0; i < n; i++) {
if (grp[i].empty()) continue;
vector<int> res = MakePath(grp[i]);
if (res.size() > best.size()) {
best = res;
}
}
return best;
}
// in contest 40
Compilation message
fish.cpp:1:10: fatal error: longesttrip.h: No such file or directory
1 | #include "longesttrip.h"
| ^~~~~~~~~~~~~~~
compilation terminated.
