| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 840155 | 2023-08-31T07:25:38 Z | happypotato | Longest Trip (IOI23_longesttrip) | C++17 | 295 ms | 780 KB |
#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];
}
}
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;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 208 KB | Output is correct |
| 2 | Correct | 3 ms | 604 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 208 KB | Output is correct |
| 2 | Correct | 1 ms | 208 KB | Output is correct |
| 3 | Correct | 1 ms | 336 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 1 ms | 464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 15 ms | 252 KB | Output is correct |
| 2 | Correct | 16 ms | 208 KB | Output is correct |
| 3 | Correct | 16 ms | 376 KB | Output is correct |
| 4 | Correct | 12 ms | 452 KB | Output is correct |
| 5 | Correct | 12 ms | 592 KB | Output is correct |
| 6 | Correct | 18 ms | 208 KB | Output is correct |
| 7 | Correct | 17 ms | 208 KB | Output is correct |
| 8 | Correct | 19 ms | 384 KB | Output is correct |
| 9 | Correct | 15 ms | 336 KB | Output is correct |
| 10 | Correct | 14 ms | 592 KB | Output is correct |
| 11 | Correct | 19 ms | 592 KB | Output is correct |
| 12 | Correct | 18 ms | 640 KB | Output is correct |
| 13 | Correct | 15 ms | 608 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 208 KB | Output is correct |
| 2 | Correct | 15 ms | 336 KB | Output is correct |
| 3 | Correct | 16 ms | 464 KB | Output is correct |
| 4 | Correct | 13 ms | 464 KB | Output is correct |
| 5 | Correct | 13 ms | 592 KB | Output is correct |
| 6 | Correct | 14 ms | 208 KB | Output is correct |
| 7 | Correct | 18 ms | 208 KB | Output is correct |
| 8 | Correct | 15 ms | 336 KB | Output is correct |
| 9 | Correct | 15 ms | 432 KB | Output is correct |
| 10 | Correct | 17 ms | 592 KB | Output is correct |
| 11 | Correct | 14 ms | 592 KB | Output is correct |
| 12 | Correct | 16 ms | 600 KB | Output is correct |
| 13 | Correct | 18 ms | 592 KB | Output is correct |
| 14 | Correct | 9 ms | 208 KB | Output is correct |
| 15 | Correct | 12 ms | 208 KB | Output is correct |
| 16 | Correct | 23 ms | 392 KB | Output is correct |
| 17 | Correct | 15 ms | 336 KB | Output is correct |
| 18 | Correct | 14 ms | 336 KB | Output is correct |
| 19 | Correct | 18 ms | 336 KB | Output is correct |
| 20 | Correct | 18 ms | 336 KB | Output is correct |
| 21 | Correct | 19 ms | 640 KB | Output is correct |
| 22 | Correct | 17 ms | 592 KB | Output is correct |
| 23 | Correct | 12 ms | 596 KB | Output is correct |
| 24 | Correct | 19 ms | 608 KB | Output is correct |
| 25 | Correct | 12 ms | 208 KB | Output is correct |
| 26 | Correct | 12 ms | 208 KB | Output is correct |
| 27 | Correct | 14 ms | 208 KB | Output is correct |
| 28 | Correct | 15 ms | 208 KB | Output is correct |
| 29 | Correct | 14 ms | 208 KB | Output is correct |
| 30 | Correct | 16 ms | 336 KB | Output is correct |
| 31 | Correct | 15 ms | 336 KB | Output is correct |
| 32 | Correct | 23 ms | 388 KB | Output is correct |
| 33 | Correct | 12 ms | 336 KB | Output is correct |
| 34 | Correct | 19 ms | 424 KB | Output is correct |
| 35 | Correct | 19 ms | 384 KB | Output is correct |
| 36 | Correct | 20 ms | 592 KB | Output is correct |
| 37 | Correct | 22 ms | 604 KB | Output is correct |
| 38 | Correct | 22 ms | 660 KB | Output is correct |
| 39 | Correct | 19 ms | 660 KB | Output is correct |
| 40 | Correct | 24 ms | 612 KB | Output is correct |
| 41 | Correct | 20 ms | 612 KB | Output is correct |
| 42 | Correct | 18 ms | 592 KB | Output is correct |
| 43 | Correct | 25 ms | 780 KB | Output is correct |
| 44 | Correct | 23 ms | 604 KB | Output is correct |
| 45 | Correct | 17 ms | 256 KB | Output is correct |
| 46 | Correct | 18 ms | 208 KB | Output is correct |
| 47 | Correct | 13 ms | 336 KB | Output is correct |
| 48 | Correct | 11 ms | 208 KB | Output is correct |
| 49 | Correct | 19 ms | 208 KB | Output is correct |
| 50 | Correct | 18 ms | 376 KB | Output is correct |
| 51 | Correct | 59 ms | 412 KB | Output is correct |
| 52 | Correct | 81 ms | 412 KB | Output is correct |
| 53 | Correct | 22 ms | 336 KB | Output is correct |
| 54 | Correct | 21 ms | 436 KB | Output is correct |
| 55 | Correct | 35 ms | 436 KB | Output is correct |
| 56 | Correct | 19 ms | 608 KB | Output is correct |
| 57 | Correct | 38 ms | 604 KB | Output is correct |
| 58 | Correct | 49 ms | 612 KB | Output is correct |
| 59 | Correct | 158 ms | 600 KB | Output is correct |
| 60 | Correct | 188 ms | 588 KB | Output is correct |
| 61 | Correct | 119 ms | 604 KB | Output is correct |
| 62 | Correct | 98 ms | 716 KB | Output is correct |
| 63 | Correct | 151 ms | 612 KB | Output is correct |
| 64 | Correct | 121 ms | 612 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 208 KB | Output is correct |
| 2 | Correct | 11 ms | 208 KB | Output is correct |
| 3 | Correct | 17 ms | 336 KB | Output is correct |
| 4 | Correct | 19 ms | 464 KB | Output is correct |
| 5 | Partially correct | 20 ms | 604 KB | Output is partially correct |
| 6 | Correct | 16 ms | 208 KB | Output is correct |
| 7 | Correct | 14 ms | 208 KB | Output is correct |
| 8 | Correct | 11 ms | 336 KB | Output is correct |
| 9 | Correct | 14 ms | 336 KB | Output is correct |
| 10 | Partially correct | 17 ms | 592 KB | Output is partially correct |
| 11 | Partially correct | 19 ms | 596 KB | Output is partially correct |
| 12 | Partially correct | 18 ms | 592 KB | Output is partially correct |
| 13 | Partially correct | 19 ms | 592 KB | Output is partially correct |
| 14 | Correct | 13 ms | 208 KB | Output is correct |
| 15 | Correct | 17 ms | 208 KB | Output is correct |
| 16 | Correct | 23 ms | 340 KB | Output is correct |
| 17 | Correct | 15 ms | 336 KB | Output is correct |
| 18 | Correct | 18 ms | 336 KB | Output is correct |
| 19 | Correct | 18 ms | 444 KB | Output is correct |
| 20 | Correct | 9 ms | 428 KB | Output is correct |
| 21 | Correct | 13 ms | 208 KB | Output is correct |
| 22 | Correct | 15 ms | 208 KB | Output is correct |
| 23 | Correct | 18 ms | 208 KB | Output is correct |
| 24 | Correct | 20 ms | 336 KB | Output is correct |
| 25 | Correct | 18 ms | 208 KB | Output is correct |
| 26 | Correct | 19 ms | 336 KB | Output is correct |
| 27 | Correct | 11 ms | 464 KB | Output is correct |
| 28 | Correct | 22 ms | 388 KB | Output is correct |
| 29 | Correct | 13 ms | 336 KB | Output is correct |
| 30 | Correct | 19 ms | 464 KB | Output is correct |
| 31 | Correct | 15 ms | 440 KB | Output is correct |
| 32 | Correct | 20 ms | 236 KB | Output is correct |
| 33 | Correct | 17 ms | 208 KB | Output is correct |
| 34 | Correct | 19 ms | 208 KB | Output is correct |
| 35 | Correct | 21 ms | 384 KB | Output is correct |
| 36 | Correct | 14 ms | 208 KB | Output is correct |
| 37 | Correct | 15 ms | 452 KB | Output is correct |
| 38 | Partially correct | 31 ms | 392 KB | Output is partially correct |
| 39 | Partially correct | 84 ms | 388 KB | Output is partially correct |
| 40 | Correct | 20 ms | 368 KB | Output is correct |
| 41 | Partially correct | 20 ms | 432 KB | Output is partially correct |
| 42 | Partially correct | 31 ms | 436 KB | Output is partially correct |
| 43 | Partially correct | 21 ms | 592 KB | Output is partially correct |
| 44 | Partially correct | 17 ms | 592 KB | Output is partially correct |
| 45 | Partially correct | 18 ms | 592 KB | Output is partially correct |
| 46 | Partially correct | 21 ms | 656 KB | Output is partially correct |
| 47 | Partially correct | 16 ms | 604 KB | Output is partially correct |
| 48 | Partially correct | 20 ms | 592 KB | Output is partially correct |
| 49 | Partially correct | 23 ms | 596 KB | Output is partially correct |
| 50 | Partially correct | 18 ms | 604 KB | Output is partially correct |
| 51 | Partially correct | 15 ms | 604 KB | Output is partially correct |
| 52 | Partially correct | 24 ms | 592 KB | Output is partially correct |
| 53 | Partially correct | 23 ms | 588 KB | Output is partially correct |
| 54 | Partially correct | 24 ms | 604 KB | Output is partially correct |
| 55 | Partially correct | 22 ms | 600 KB | Output is partially correct |
| 56 | Partially correct | 14 ms | 604 KB | Output is partially correct |
| 57 | Partially correct | 15 ms | 604 KB | Output is partially correct |
| 58 | Partially correct | 23 ms | 592 KB | Output is partially correct |
| 59 | Partially correct | 18 ms | 608 KB | Output is partially correct |
| 60 | Partially correct | 20 ms | 604 KB | Output is partially correct |
| 61 | Partially correct | 23 ms | 604 KB | Output is partially correct |
| 62 | Partially correct | 20 ms | 592 KB | Output is partially correct |
| 63 | Partially correct | 28 ms | 648 KB | Output is partially correct |
| 64 | Partially correct | 66 ms | 636 KB | Output is partially correct |
| 65 | Partially correct | 182 ms | 592 KB | Output is partially correct |
| 66 | Partially correct | 151 ms | 604 KB | Output is partially correct |
| 67 | Partially correct | 103 ms | 604 KB | Output is partially correct |
| 68 | Partially correct | 95 ms | 604 KB | Output is partially correct |
| 69 | Partially correct | 126 ms | 588 KB | Output is partially correct |
| 70 | Partially correct | 128 ms | 604 KB | Output is partially correct |
| 71 | Partially correct | 56 ms | 600 KB | Output is partially correct |
| 72 | Partially correct | 98 ms | 608 KB | Output is partially correct |
| 73 | Partially correct | 181 ms | 600 KB | Output is partially correct |
| 74 | Partially correct | 224 ms | 600 KB | Output is partially correct |
| 75 | Partially correct | 295 ms | 640 KB | Output is partially correct |
| 76 | Partially correct | 239 ms | 608 KB | Output is partially correct |
| 77 | Partially correct | 46 ms | 628 KB | Output is partially correct |
| 78 | Partially correct | 57 ms | 600 KB | Output is partially correct |
| 79 | Partially correct | 248 ms | 596 KB | Output is partially correct |
| 80 | Partially correct | 123 ms | 616 KB | Output is partially correct |
| 81 | Partially correct | 160 ms | 604 KB | Output is partially correct |
| 82 | Partially correct | 175 ms | 604 KB | Output is partially correct |