| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 840075 | 2023-08-31T05:50:55 Z | happypotato | Longest Trip (IOI23_longesttrip) | C++17 | 1000 ms | 492 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];
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 {
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;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (are_connected({i}, {j})) {
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;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 180 ms | 364 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 208 KB | Output is correct |
| 2 | Correct | 1 ms | 208 KB | Output is correct |
| 3 | Correct | 1 ms | 208 KB | Output is correct |
| 4 | Correct | 1 ms | 336 KB | Output is correct |
| 5 | Correct | 1 ms | 308 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 208 KB | Output is correct |
| 2 | Correct | 44 ms | 208 KB | Output is correct |
| 3 | Correct | 161 ms | 332 KB | Output is correct |
| 4 | Correct | 425 ms | 336 KB | Output is correct |
| 5 | Correct | 961 ms | 364 KB | Output is correct |
| 6 | Correct | 9 ms | 208 KB | Output is correct |
| 7 | Correct | 41 ms | 208 KB | Output is correct |
| 8 | Correct | 136 ms | 336 KB | Output is correct |
| 9 | Correct | 397 ms | 336 KB | Output is correct |
| 10 | Correct | 870 ms | 360 KB | Output is correct |
| 11 | Correct | 746 ms | 380 KB | Output is correct |
| 12 | Correct | 749 ms | 368 KB | Output is correct |
| 13 | Correct | 819 ms | 364 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 208 KB | Output is correct |
| 2 | Correct | 33 ms | 208 KB | Output is correct |
| 3 | Correct | 201 ms | 208 KB | Output is correct |
| 4 | Correct | 452 ms | 340 KB | Output is correct |
| 5 | Correct | 744 ms | 360 KB | Output is correct |
| 6 | Correct | 12 ms | 208 KB | Output is correct |
| 7 | Correct | 26 ms | 208 KB | Output is correct |
| 8 | Correct | 165 ms | 336 KB | Output is correct |
| 9 | Correct | 309 ms | 336 KB | Output is correct |
| 10 | Correct | 808 ms | 360 KB | Output is correct |
| 11 | Correct | 792 ms | 364 KB | Output is correct |
| 12 | Correct | 923 ms | 368 KB | Output is correct |
| 13 | Correct | 996 ms | 368 KB | Output is correct |
| 14 | Correct | 9 ms | 208 KB | Output is correct |
| 15 | Correct | 18 ms | 208 KB | Output is correct |
| 16 | Correct | 59 ms | 208 KB | Output is correct |
| 17 | Correct | 136 ms | 208 KB | Output is correct |
| 18 | Correct | 172 ms | 336 KB | Output is correct |
| 19 | Correct | 291 ms | 336 KB | Output is correct |
| 20 | Correct | 369 ms | 336 KB | Output is correct |
| 21 | Correct | 938 ms | 368 KB | Output is correct |
| 22 | Correct | 858 ms | 360 KB | Output is correct |
| 23 | Correct | 941 ms | 368 KB | Output is correct |
| 24 | Correct | 684 ms | 372 KB | Output is correct |
| 25 | Correct | 16 ms | 208 KB | Output is correct |
| 26 | Correct | 11 ms | 208 KB | Output is correct |
| 27 | Correct | 21 ms | 208 KB | Output is correct |
| 28 | Correct | 25 ms | 208 KB | Output is correct |
| 29 | Correct | 43 ms | 208 KB | Output is correct |
| 30 | Correct | 193 ms | 336 KB | Output is correct |
| 31 | Correct | 179 ms | 336 KB | Output is correct |
| 32 | Correct | 212 ms | 336 KB | Output is correct |
| 33 | Correct | 257 ms | 336 KB | Output is correct |
| 34 | Correct | 308 ms | 336 KB | Output is correct |
| 35 | Correct | 332 ms | 336 KB | Output is correct |
| 36 | Correct | 903 ms | 336 KB | Output is correct |
| 37 | Execution timed out | 1108 ms | 368 KB | Time limit exceeded |
| 38 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 208 KB | Output is correct |
| 2 | Correct | 36 ms | 208 KB | Output is correct |
| 3 | Partially correct | 142 ms | 208 KB | Output is partially correct |
| 4 | Partially correct | 405 ms | 336 KB | Output is partially correct |
| 5 | Partially correct | 898 ms | 360 KB | Output is partially correct |
| 6 | Correct | 15 ms | 208 KB | Output is correct |
| 7 | Correct | 29 ms | 208 KB | Output is correct |
| 8 | Partially correct | 198 ms | 208 KB | Output is partially correct |
| 9 | Partially correct | 356 ms | 336 KB | Output is partially correct |
| 10 | Partially correct | 1000 ms | 368 KB | Output is partially correct |
| 11 | Partially correct | 783 ms | 368 KB | Output is partially correct |
| 12 | Partially correct | 980 ms | 364 KB | Output is partially correct |
| 13 | Partially correct | 820 ms | 336 KB | Output is partially correct |
| 14 | Correct | 8 ms | 208 KB | Output is correct |
| 15 | Correct | 21 ms | 208 KB | Output is correct |
| 16 | Correct | 46 ms | 208 KB | Output is correct |
| 17 | Partially correct | 95 ms | 208 KB | Output is partially correct |
| 18 | Partially correct | 121 ms | 336 KB | Output is partially correct |
| 19 | Partially correct | 269 ms | 336 KB | Output is partially correct |
| 20 | Partially correct | 317 ms | 336 KB | Output is partially correct |
| 21 | Correct | 15 ms | 208 KB | Output is correct |
| 22 | Correct | 11 ms | 208 KB | Output is correct |
| 23 | Correct | 27 ms | 208 KB | Output is correct |
| 24 | Correct | 24 ms | 208 KB | Output is correct |
| 25 | Correct | 24 ms | 208 KB | Output is correct |
| 26 | Partially correct | 204 ms | 336 KB | Output is partially correct |
| 27 | Partially correct | 205 ms | 336 KB | Output is partially correct |
| 28 | Partially correct | 210 ms | 336 KB | Output is partially correct |
| 29 | Partially correct | 283 ms | 336 KB | Output is partially correct |
| 30 | Partially correct | 259 ms | 336 KB | Output is partially correct |
| 31 | Partially correct | 279 ms | 336 KB | Output is partially correct |
| 32 | Correct | 9 ms | 208 KB | Output is correct |
| 33 | Correct | 10 ms | 208 KB | Output is correct |
| 34 | Correct | 33 ms | 208 KB | Output is correct |
| 35 | Correct | 34 ms | 208 KB | Output is correct |
| 36 | Correct | 25 ms | 208 KB | Output is correct |
| 37 | Partially correct | 165 ms | 208 KB | Output is partially correct |
| 38 | Partially correct | 214 ms | 336 KB | Output is partially correct |
| 39 | Partially correct | 202 ms | 336 KB | Output is partially correct |
| 40 | Partially correct | 322 ms | 336 KB | Output is partially correct |
| 41 | Partially correct | 322 ms | 336 KB | Output is partially correct |
| 42 | Partially correct | 318 ms | 336 KB | Output is partially correct |
| 43 | Partially correct | 842 ms | 368 KB | Output is partially correct |
| 44 | Partially correct | 781 ms | 364 KB | Output is partially correct |
| 45 | Partially correct | 803 ms | 368 KB | Output is partially correct |
| 46 | Partially correct | 873 ms | 376 KB | Output is partially correct |
| 47 | Partially correct | 849 ms | 372 KB | Output is partially correct |
| 48 | Partially correct | 791 ms | 360 KB | Output is partially correct |
| 49 | Partially correct | 679 ms | 364 KB | Output is partially correct |
| 50 | Partially correct | 697 ms | 368 KB | Output is partially correct |
| 51 | Partially correct | 736 ms | 372 KB | Output is partially correct |
| 52 | Partially correct | 778 ms | 364 KB | Output is partially correct |
| 53 | Partially correct | 788 ms | 360 KB | Output is partially correct |
| 54 | Partially correct | 751 ms | 380 KB | Output is partially correct |
| 55 | Partially correct | 696 ms | 376 KB | Output is partially correct |
| 56 | Partially correct | 687 ms | 360 KB | Output is partially correct |
| 57 | Partially correct | 744 ms | 368 KB | Output is partially correct |
| 58 | Partially correct | 744 ms | 360 KB | Output is partially correct |
| 59 | Partially correct | 799 ms | 372 KB | Output is partially correct |
| 60 | Partially correct | 704 ms | 360 KB | Output is partially correct |
| 61 | Partially correct | 750 ms | 360 KB | Output is partially correct |
| 62 | Partially correct | 780 ms | 368 KB | Output is partially correct |
| 63 | Partially correct | 806 ms | 376 KB | Output is partially correct |
| 64 | Partially correct | 773 ms | 372 KB | Output is partially correct |
| 65 | Partially correct | 796 ms | 376 KB | Output is partially correct |
| 66 | Partially correct | 756 ms | 376 KB | Output is partially correct |
| 67 | Partially correct | 787 ms | 360 KB | Output is partially correct |
| 68 | Partially correct | 806 ms | 376 KB | Output is partially correct |
| 69 | Partially correct | 833 ms | 492 KB | Output is partially correct |
| 70 | Partially correct | 777 ms | 372 KB | Output is partially correct |
| 71 | Partially correct | 854 ms | 376 KB | Output is partially correct |
| 72 | Partially correct | 706 ms | 336 KB | Output is partially correct |
| 73 | Partially correct | 911 ms | 380 KB | Output is partially correct |
| 74 | Partially correct | 779 ms | 364 KB | Output is partially correct |
| 75 | Partially correct | 809 ms | 384 KB | Output is partially correct |
| 76 | Partially correct | 834 ms | 368 KB | Output is partially correct |
| 77 | Partially correct | 738 ms | 380 KB | Output is partially correct |
| 78 | Partially correct | 685 ms | 364 KB | Output is partially correct |
| 79 | Partially correct | 638 ms | 368 KB | Output is partially correct |
| 80 | Partially correct | 782 ms | 360 KB | Output is partially correct |
| 81 | Partially correct | 799 ms | 376 KB | Output is partially correct |
| 82 | Partially correct | 901 ms | 404 KB | Output is partially correct |