| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 840150 | happypotato | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
bool con(int x, int y) {
if (conn[x][y] != -1) return conn[x][y];
return (conn[x][y] = conn[y][x] = 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() {
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];
} else {
while (true) continue;
}
}
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])) {
// 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;
}
if (!found) {
while (true) continue;
}
}
// 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();
if (D == 3) {
vector<int> res(n);
for (int i = 0; i < n; i++) res[i] = i;
return res;
}
queue<int> q;
for (int i = 0; i < n; i++) {
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();
if (are_connected(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 (are_connected(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 (are_connected(grp[fina], grp[finb])) {
DSUMerge(fina, finb);
for (int &x : grp[finb]) grp[fina].pb(x);
grp[finb].clear();
}
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;
}