#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
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];
int conn[mxN][mxN];
int callcnt;
bool con(int x, int y) {
// cerr << "CALLx " << x << ' ' << y << endl;
if (x == y) return (conn[x][x] = 1);
if (conn[x][y] != -1) return conn[x][y];
callcnt++;
return (conn[x][y] = conn[y][x] = are_connected({x}, {y}));
}
bool Con(vector<int> x, vector<int> y) {
if (x.size() == 1 && y.size() == 1) {
return con(x[0], y[0]);
}
// cerr << "CALL\n";
// for (int &cur : x) cerr << cur << ' ';
// cerr << endl;
// for (int &cur : y) cerr << cur << ' ';
// cerr << endl;
callcnt++;
return are_connected(x, y);
}
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() {
callcnt = 0;
for (int i = 0; i < n; i++) {
adj[i].clear();
grp[i].clear();
for (int j = 0; j < n; j++) {
conn[i][j] = -1;
}
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 {
conn[cur.ss.ff][v[i]] = conn[v[i]][cur.ss.ff] = 1;
nxt[cur.ss.ff].pb(v[i]);
nxt[v[i]].pb(cur.ss.ff);
cur.ss.ff = v[i];
}
}
if (!Con({cur.ff.ff, cur.ff.ss}, {cur.ss.ff, cur.ss.ss})) {
vector<int> res[2];
res[0] = GetPath(cur.ff.ff);
res[1] = GetPath(cur.ss.ff);
return (res[0].size() >= res[1].size() ? res[0] : res[1]);
}
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);
vector<int> take[2];
take[0] = res[0];
take[1] = res[1];
// cerr << "res0: ";
// for (int &x : res[0]) cerr << x << ' ';
// cerr << endl;
// cerr << "res1: ";
// for (int &x : res[1]) cerr << x << ' ';
// cerr << endl;
set<int> s; for(auto i : take[0]) s.insert(i);
for(auto i : take[1]) assert(!s.count(i));
vector<int> split[2];
while (take[0].size() >= 2) {
split[0].clear();
split[1].clear();
int cut = (int)(take[0].size()) / 2;
for (int i = 0; i < cut; i++) split[0].pb(take[0][i]);
for (int i = cut; i < (int)(take[0].size()); i++) split[1].pb(take[0][i]);
if (Con(split[0], take[1])) take[0] = split[0];
else take[0] = split[1];
}
while (take[1].size() >= 2) {
split[0].clear();
split[1].clear();
int cut = (int)(take[1].size()) / 2;
for (int i = 0; i < cut; i++) split[0].pb(take[1][i]);
for (int i = cut; i < (int)(take[1].size()); i++) split[1].pb(take[1][i]);
if (Con(take[0], split[0])) take[1] = split[0];
else take[1] = split[1];
}
bool found = false;
for (int i = 0; i < (int)(res[0].size()); i++) {
if (res[0][i] != take[0][0]) continue;
for (int j = 0; j < (int)(res[1].size()); j++) {
if (res[1][j] != take[1][0]) continue;
if (true) {
// cerr << "FOUND " << res[0][i] << ' ' << res[1][j] << endl;
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);
// cerr << "RES0 ";
// for (int &x : res[0]) cerr << x << ' ';
// cerr << endl;
st = (i == 0 ? res[0].back() : res[0][i - 1]);
// cerr << "ST " << st << endl;
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;
}
// cerr << "END\n";
}
// cerr << "find path for: ";
// for (int &x : v) cerr << x << ' ';
// cerr << endl;
vector<int> res = GetPath(st);
// cerr << "st: " << st << endl;
// cerr << "result: ";
// for (int &x : res) cerr << x << ' ';
// cerr << endl;
return res;
}
vector<int> longest_trip(int N, int D)
{
n = N;
reset();
// queue<int> q;
// for (int i = 0; i < n; i++) {
// grp[i].clear();
// grp[i].pb(i);
// q.push(i);
// }
// while (q.size() >= 3) {
// int a = q.front(); q.pop();
// int b = q.front(); q.pop();
// int c = q.front(); q.pop();
// // cerr << a << ' ' << b << ' ' << c << endl;
// if (Con(grp[a], grp[b])) {
// DSUMerge(a, b);
// for (int &x : grp[b]) grp[a].pb(x);
// grp[b].clear();
// q.push(a);
// q.push(c);
// } else if (Con(grp[a], grp[c])) {
// DSUMerge(a, c);
// for (int &x : grp[c]) grp[a].pb(x);
// grp[c].clear();
// q.push(a);
// q.push(b);
// } else {
// DSUMerge(b, c);
// for (int &x : grp[c]) grp[b].pb(x);
// grp[c].clear();
// q.push(a);
// q.push(b);
// }
// }
// int fina = q.front(); q.pop();
// int finb = q.front(); q.pop();
// if (Con(grp[fina], grp[finb])) {
// DSUMerge(fina, finb);
// for (int &x : grp[finb]) grp[fina].pb(x);
// grp[finb].clear();
// }
// // cerr << "CALLCNT " << callcnt << endl;
// 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;
vector<int> res(n);
for (int i = 0; i < n; i++) res[i] = i;
return MakePath(res);
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> MakePath(std::vector<int>&)':
longesttrip.cpp:247:30: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
247 | vector<int> res = GetPath(st);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
invalid array |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
208 KB |
invalid array |
| 3 |
Halted |
0 ms |
0 KB |
- |
