| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839898 | 2023-08-30T20:29:03 Z | happypotato | Longest Trip (IOI23_longesttrip) | C++17 | 1000 ms | 896 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})) {
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;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 214 ms | 676 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 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 | 336 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 12 ms | 208 KB | Output is correct |
| 2 | Correct | 30 ms | 208 KB | Output is correct |
| 3 | Correct | 154 ms | 336 KB | Output is correct |
| 4 | Correct | 530 ms | 336 KB | Output is correct |
| 5 | Correct | 913 ms | 896 KB | Output is correct |
| 6 | Correct | 12 ms | 208 KB | Output is correct |
| 7 | Correct | 30 ms | 208 KB | Output is correct |
| 8 | Correct | 129 ms | 476 KB | Output is correct |
| 9 | Correct | 304 ms | 336 KB | Output is correct |
| 10 | Correct | 814 ms | 576 KB | Output is correct |
| 11 | Correct | 775 ms | 700 KB | Output is correct |
| 12 | Correct | 786 ms | 656 KB | Output is correct |
| 13 | Correct | 899 ms | 656 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 208 KB | Output is correct |
| 2 | Correct | 42 ms | 208 KB | Output is correct |
| 3 | Correct | 148 ms | 344 KB | Output is correct |
| 4 | Correct | 342 ms | 460 KB | Output is correct |
| 5 | Correct | 756 ms | 568 KB | Output is correct |
| 6 | Correct | 12 ms | 208 KB | Output is correct |
| 7 | Correct | 42 ms | 208 KB | Output is correct |
| 8 | Correct | 174 ms | 336 KB | Output is correct |
| 9 | Correct | 353 ms | 336 KB | Output is correct |
| 10 | Execution timed out | 1111 ms | 640 KB | Time limit exceeded |
| 11 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 208 KB | Output is correct |
| 2 | Correct | 22 ms | 208 KB | Output is correct |
| 3 | Partially correct | 191 ms | 336 KB | Output is partially correct |
| 4 | Partially correct | 400 ms | 388 KB | Output is partially correct |
| 5 | Partially correct | 956 ms | 692 KB | Output is partially correct |
| 6 | Correct | 11 ms | 208 KB | Output is correct |
| 7 | Correct | 42 ms | 208 KB | Output is correct |
| 8 | Partially correct | 223 ms | 336 KB | Output is partially correct |
| 9 | Partially correct | 373 ms | 372 KB | Output is partially correct |
| 10 | Partially correct | 817 ms | 568 KB | Output is partially correct |
| 11 | Partially correct | 927 ms | 656 KB | Output is partially correct |
| 12 | Partially correct | 744 ms | 584 KB | Output is partially correct |
| 13 | Partially correct | 670 ms | 656 KB | Output is partially correct |
| 14 | Correct | 13 ms | 208 KB | Output is correct |
| 15 | Correct | 18 ms | 208 KB | Output is correct |
| 16 | Correct | 72 ms | 208 KB | Output is correct |
| 17 | Partially correct | 117 ms | 336 KB | Output is partially correct |
| 18 | Partially correct | 211 ms | 404 KB | Output is partially correct |
| 19 | Partially correct | 228 ms | 336 KB | Output is partially correct |
| 20 | Partially correct | 226 ms | 464 KB | Output is partially correct |
| 21 | Correct | 17 ms | 208 KB | Output is correct |
| 22 | Correct | 16 ms | 208 KB | Output is correct |
| 23 | Correct | 30 ms | 208 KB | Output is correct |
| 24 | Correct | 42 ms | 208 KB | Output is correct |
| 25 | Correct | 43 ms | 208 KB | Output is correct |
| 26 | Partially correct | 183 ms | 340 KB | Output is partially correct |
| 27 | Partially correct | 239 ms | 336 KB | Output is partially correct |
| 28 | Partially correct | 269 ms | 456 KB | Output is partially correct |
| 29 | Partially correct | 335 ms | 352 KB | Output is partially correct |
| 30 | Partially correct | 379 ms | 380 KB | Output is partially correct |
| 31 | Partially correct | 341 ms | 392 KB | Output is partially correct |
| 32 | Correct | 12 ms | 208 KB | Output is correct |
| 33 | Correct | 10 ms | 208 KB | Output is correct |
| 34 | Correct | 27 ms | 208 KB | Output is correct |
| 35 | Correct | 23 ms | 208 KB | Output is correct |
| 36 | Correct | 29 ms | 208 KB | Output is correct |
| 37 | Partially correct | 196 ms | 584 KB | Output is partially correct |
| 38 | Partially correct | 210 ms | 336 KB | Output is partially correct |
| 39 | Partially correct | 211 ms | 336 KB | Output is partially correct |
| 40 | Partially correct | 337 ms | 388 KB | Output is partially correct |
| 41 | Partially correct | 305 ms | 336 KB | Output is partially correct |
| 42 | Partially correct | 298 ms | 336 KB | Output is partially correct |
| 43 | Partially correct | 827 ms | 620 KB | Output is partially correct |
| 44 | Partially correct | 747 ms | 692 KB | Output is partially correct |
| 45 | Partially correct | 796 ms | 732 KB | Output is partially correct |
| 46 | Partially correct | 657 ms | 680 KB | Output is partially correct |
| 47 | Partially correct | 779 ms | 652 KB | Output is partially correct |
| 48 | Partially correct | 794 ms | 712 KB | Output is partially correct |
| 49 | Partially correct | 787 ms | 652 KB | Output is partially correct |
| 50 | Partially correct | 881 ms | 664 KB | Output is partially correct |
| 51 | Partially correct | 901 ms | 652 KB | Output is partially correct |
| 52 | Partially correct | 893 ms | 512 KB | Output is partially correct |
| 53 | Partially correct | 919 ms | 676 KB | Output is partially correct |
| 54 | Partially correct | 852 ms | 648 KB | Output is partially correct |
| 55 | Partially correct | 862 ms | 752 KB | Output is partially correct |
| 56 | Partially correct | 956 ms | 644 KB | Output is partially correct |
| 57 | Partially correct | 995 ms | 660 KB | Output is partially correct |
| 58 | Partially correct | 837 ms | 848 KB | Output is partially correct |
| 59 | Execution timed out | 1042 ms | 680 KB | Time limit exceeded |
| 60 | Halted | 0 ms | 0 KB | - |