| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 844834 | 2023-09-06T03:29:11 Z | vjudge1 | Longest Trip (IOI23_longesttrip) | C++17 | 746 ms | 2228 KB |
#include "longesttrip.h"
// 123
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D) {
if (D == 3) {
vector<int> ans(N);
iota(ans.begin(), ans.end(), 0);
return ans;
} else {
vector<vector<int>> d(N, vector<int>(N));
vector<vector<int>> adj(N);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (are_connected({i}, {j})) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
d[i][j] = d[j][i] = 1;
}
}
}
if (D == 2) {
vector<int> ans(1, 0);
vector<int> vis(N, 0);
vis[0] = 1;
while (ans.size() + 2 <= N) {
int i = 0, j = 0;
for (; i < N; i++) {
if (vis[i] == 0) break;
}
for (j = i + 1; j < N; j++) {
if (vis[j] == 0) break;
}
assert(i < N && j < N);
int x = ans.back();
if (d[x][i] && d[i][j]) {
ans.emplace_back(i), ans.emplace_back(j);
vis[i] = vis[j] = 1;
} else if (d[x][j] && d[j][i]) {
ans.emplace_back(j), ans.emplace_back(i);
vis[i] = vis[j] = 1;
} else {
assert(d[x][i] && d[x][j]);
ans.emplace_back(i);
vis[i] = 1;
}
}
int i = 0;
for (; i < N; i++) {
if (vis[i] == 0) break;
}
if (ans.size() == N - 1) {
if (d[ans.back()][i]) {
ans.emplace_back(i);
} else if (d[ans.front()][i]) {
ans.insert(ans.begin(), i);
} else {
assert(0);
}
}
return ans;
} else {
vector<int> vis(N, 0);
int cc = 0;
vector<int> ls[2];
function<void(int, vector<int>&)> dfs = [&](int u, vector<int>& ls) {
vis[u] = 1;
ls.emplace_back(u);
for (int v : adj[u]) {
if (!vis[v]) dfs(v, ls);
}
};
for (int i = 0; i < N; i++) {
if (!vis[i]) dfs(i, ls[cc++]);
}
if (cc == 2) {
if (ls[0].size() < ls[1].size()) swap(ls[0], ls[1]);
return ls[0];
}
deque<int> ans;
auto add = [&](int x, int _) {
if (_) {
ans.emplace_back(x);
} else {
ans.emplace_front(x);
}
};
auto rotate = [&](int x) {
deque<int> tmp;
while (ans.back() != x) {
tmp.emplace_back(ans.back());
ans.pop_back();
}
ans.pop_back();
tmp.emplace_back(x);
while (ans.size()) {
tmp.emplace_front(ans.front());
ans.pop_front();
}
ans = tmp;
};
function<void(int, int)> solve = [&](int u, int _) {
vis[u] = 0;
add(u, _);
int fst = 1;
for (int v : adj[u]) {
if (vis[v] == 0) continue;
if (fst) {
solve(v, _);
} else {
int x = ans.front();
int y = ans.back();
if (d[x][v]) {
solve(v, 0);
} else if (d[y][v]) {
solve(v, 1);
} else {
assert(d[x][y]);
rotate(u);
solve(v, 1);
}
}
fst = 0;
}
};
solve(0, 0);
vector<int> res;
for (int i : ans) res.emplace_back(i);
return res;
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 157 ms | 1676 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 344 KB | Output is correct |
| 2 | Correct | 1 ms | 344 KB | Output is correct |
| 3 | Correct | 0 ms | 344 KB | Output is correct |
| 4 | Correct | 0 ms | 344 KB | Output is correct |
| 5 | Correct | 1 ms | 344 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 344 KB | Output is correct |
| 2 | Correct | 25 ms | 344 KB | Output is correct |
| 3 | Correct | 130 ms | 700 KB | Output is correct |
| 4 | Correct | 331 ms | 800 KB | Output is correct |
| 5 | Correct | 739 ms | 1264 KB | Output is correct |
| 6 | Correct | 8 ms | 344 KB | Output is correct |
| 7 | Correct | 24 ms | 344 KB | Output is correct |
| 8 | Correct | 144 ms | 600 KB | Output is correct |
| 9 | Correct | 277 ms | 748 KB | Output is correct |
| 10 | Correct | 669 ms | 1712 KB | Output is correct |
| 11 | Correct | 704 ms | 1624 KB | Output is correct |
| 12 | Correct | 736 ms | 1652 KB | Output is correct |
| 13 | Correct | 739 ms | 1852 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 344 KB | Output is correct |
| 2 | Correct | 27 ms | 344 KB | Output is correct |
| 3 | Correct | 130 ms | 724 KB | Output is correct |
| 4 | Correct | 363 ms | 1372 KB | Output is correct |
| 5 | Correct | 715 ms | 1672 KB | Output is correct |
| 6 | Correct | 7 ms | 344 KB | Output is correct |
| 7 | Correct | 23 ms | 344 KB | Output is correct |
| 8 | Correct | 122 ms | 856 KB | Output is correct |
| 9 | Correct | 259 ms | 1268 KB | Output is correct |
| 10 | Correct | 708 ms | 1652 KB | Output is correct |
| 11 | Correct | 746 ms | 1464 KB | Output is correct |
| 12 | Correct | 717 ms | 1772 KB | Output is correct |
| 13 | Correct | 691 ms | 1600 KB | Output is correct |
| 14 | Correct | 6 ms | 344 KB | Output is correct |
| 15 | Correct | 10 ms | 600 KB | Output is correct |
| 16 | Correct | 35 ms | 344 KB | Output is correct |
| 17 | Correct | 88 ms | 600 KB | Output is correct |
| 18 | Correct | 141 ms | 960 KB | Output is correct |
| 19 | Correct | 268 ms | 904 KB | Output is correct |
| 20 | Correct | 253 ms | 1272 KB | Output is correct |
| 21 | Correct | 740 ms | 1860 KB | Output is correct |
| 22 | Correct | 743 ms | 1696 KB | Output is correct |
| 23 | Correct | 672 ms | 1836 KB | Output is correct |
| 24 | Correct | 746 ms | 1872 KB | Output is correct |
| 25 | Correct | 7 ms | 344 KB | Output is correct |
| 26 | Correct | 7 ms | 344 KB | Output is correct |
| 27 | Correct | 23 ms | 344 KB | Output is correct |
| 28 | Correct | 23 ms | 344 KB | Output is correct |
| 29 | Correct | 21 ms | 344 KB | Output is correct |
| 30 | Correct | 150 ms | 600 KB | Output is correct |
| 31 | Correct | 172 ms | 1224 KB | Output is correct |
| 32 | Correct | 169 ms | 716 KB | Output is correct |
| 33 | Correct | 255 ms | 1012 KB | Output is correct |
| 34 | Correct | 247 ms | 1016 KB | Output is correct |
| 35 | Correct | 257 ms | 1268 KB | Output is correct |
| 36 | Correct | 716 ms | 1460 KB | Output is correct |
| 37 | Correct | 710 ms | 1364 KB | Output is correct |
| 38 | Correct | 719 ms | 1372 KB | Output is correct |
| 39 | Correct | 665 ms | 1372 KB | Output is correct |
| 40 | Correct | 734 ms | 2020 KB | Output is correct |
| 41 | Correct | 686 ms | 1272 KB | Output is correct |
| 42 | Correct | 705 ms | 1732 KB | Output is correct |
| 43 | Correct | 677 ms | 1800 KB | Output is correct |
| 44 | Correct | 724 ms | 1592 KB | Output is correct |
| 45 | Correct | 9 ms | 344 KB | Output is correct |
| 46 | Correct | 12 ms | 344 KB | Output is correct |
| 47 | Correct | 29 ms | 344 KB | Output is correct |
| 48 | Correct | 24 ms | 344 KB | Output is correct |
| 49 | Correct | 22 ms | 344 KB | Output is correct |
| 50 | Correct | 155 ms | 712 KB | Output is correct |
| 51 | Correct | 160 ms | 1224 KB | Output is correct |
| 52 | Correct | 162 ms | 972 KB | Output is correct |
| 53 | Correct | 269 ms | 664 KB | Output is correct |
| 54 | Correct | 256 ms | 928 KB | Output is correct |
| 55 | Correct | 251 ms | 856 KB | Output is correct |
| 56 | Correct | 718 ms | 1320 KB | Output is correct |
| 57 | Correct | 685 ms | 1420 KB | Output is correct |
| 58 | Correct | 681 ms | 1828 KB | Output is correct |
| 59 | Correct | 684 ms | 2064 KB | Output is correct |
| 60 | Correct | 657 ms | 1368 KB | Output is correct |
| 61 | Correct | 671 ms | 1348 KB | Output is correct |
| 62 | Correct | 711 ms | 1276 KB | Output is correct |
| 63 | Correct | 708 ms | 1368 KB | Output is correct |
| 64 | Correct | 672 ms | 2060 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 344 KB | Output is correct |
| 2 | Correct | 20 ms | 596 KB | Output is correct |
| 3 | Partially correct | 113 ms | 968 KB | Output is partially correct |
| 4 | Partially correct | 328 ms | 896 KB | Output is partially correct |
| 5 | Partially correct | 676 ms | 2144 KB | Output is partially correct |
| 6 | Correct | 6 ms | 344 KB | Output is correct |
| 7 | Correct | 24 ms | 344 KB | Output is correct |
| 8 | Partially correct | 119 ms | 864 KB | Output is partially correct |
| 9 | Partially correct | 254 ms | 1384 KB | Output is partially correct |
| 10 | Partially correct | 697 ms | 1652 KB | Output is partially correct |
| 11 | Partially correct | 724 ms | 1400 KB | Output is partially correct |
| 12 | Partially correct | 680 ms | 1368 KB | Output is partially correct |
| 13 | Partially correct | 679 ms | 1532 KB | Output is partially correct |
| 14 | Correct | 7 ms | 344 KB | Output is correct |
| 15 | Correct | 11 ms | 436 KB | Output is correct |
| 16 | Correct | 36 ms | 600 KB | Output is correct |
| 17 | Partially correct | 69 ms | 856 KB | Output is partially correct |
| 18 | Partially correct | 108 ms | 864 KB | Output is partially correct |
| 19 | Partially correct | 256 ms | 868 KB | Output is partially correct |
| 20 | Partially correct | 223 ms | 1512 KB | Output is partially correct |
| 21 | Correct | 10 ms | 344 KB | Output is correct |
| 22 | Correct | 7 ms | 344 KB | Output is correct |
| 23 | Correct | 22 ms | 344 KB | Output is correct |
| 24 | Correct | 24 ms | 344 KB | Output is correct |
| 25 | Correct | 22 ms | 344 KB | Output is correct |
| 26 | Partially correct | 151 ms | 708 KB | Output is partially correct |
| 27 | Partially correct | 163 ms | 972 KB | Output is partially correct |
| 28 | Partially correct | 153 ms | 964 KB | Output is partially correct |
| 29 | Partially correct | 260 ms | 780 KB | Output is partially correct |
| 30 | Partially correct | 256 ms | 1032 KB | Output is partially correct |
| 31 | Partially correct | 246 ms | 1116 KB | Output is partially correct |
| 32 | Correct | 9 ms | 344 KB | Output is correct |
| 33 | Correct | 8 ms | 344 KB | Output is correct |
| 34 | Correct | 19 ms | 344 KB | Output is correct |
| 35 | Correct | 23 ms | 344 KB | Output is correct |
| 36 | Correct | 19 ms | 344 KB | Output is correct |
| 37 | Partially correct | 153 ms | 1228 KB | Output is partially correct |
| 38 | Partially correct | 160 ms | 712 KB | Output is partially correct |
| 39 | Partially correct | 151 ms | 708 KB | Output is partially correct |
| 40 | Partially correct | 249 ms | 856 KB | Output is partially correct |
| 41 | Partially correct | 251 ms | 1380 KB | Output is partially correct |
| 42 | Partially correct | 262 ms | 1272 KB | Output is partially correct |
| 43 | Partially correct | 690 ms | 2092 KB | Output is partially correct |
| 44 | Partially correct | 671 ms | 2168 KB | Output is partially correct |
| 45 | Partially correct | 657 ms | 1912 KB | Output is partially correct |
| 46 | Partially correct | 699 ms | 1704 KB | Output is partially correct |
| 47 | Partially correct | 730 ms | 1860 KB | Output is partially correct |
| 48 | Partially correct | 697 ms | 1132 KB | Output is partially correct |
| 49 | Partially correct | 714 ms | 1368 KB | Output is partially correct |
| 50 | Partially correct | 691 ms | 1620 KB | Output is partially correct |
| 51 | Partially correct | 673 ms | 2120 KB | Output is partially correct |
| 52 | Partially correct | 675 ms | 1764 KB | Output is partially correct |
| 53 | Partially correct | 701 ms | 1544 KB | Output is partially correct |
| 54 | Partially correct | 706 ms | 2076 KB | Output is partially correct |
| 55 | Partially correct | 735 ms | 2228 KB | Output is partially correct |
| 56 | Partially correct | 692 ms | 1288 KB | Output is partially correct |
| 57 | Partially correct | 684 ms | 1572 KB | Output is partially correct |
| 58 | Partially correct | 689 ms | 2028 KB | Output is partially correct |
| 59 | Partially correct | 689 ms | 2116 KB | Output is partially correct |
| 60 | Partially correct | 724 ms | 1496 KB | Output is partially correct |
| 61 | Partially correct | 725 ms | 1516 KB | Output is partially correct |
| 62 | Partially correct | 741 ms | 2120 KB | Output is partially correct |
| 63 | Partially correct | 719 ms | 1388 KB | Output is partially correct |
| 64 | Partially correct | 725 ms | 1624 KB | Output is partially correct |
| 65 | Partially correct | 657 ms | 1856 KB | Output is partially correct |
| 66 | Partially correct | 675 ms | 2028 KB | Output is partially correct |
| 67 | Partially correct | 695 ms | 1536 KB | Output is partially correct |
| 68 | Partially correct | 691 ms | 1772 KB | Output is partially correct |
| 69 | Partially correct | 703 ms | 1920 KB | Output is partially correct |
| 70 | Partially correct | 668 ms | 1556 KB | Output is partially correct |
| 71 | Partially correct | 696 ms | 1292 KB | Output is partially correct |
| 72 | Partially correct | 678 ms | 1996 KB | Output is partially correct |
| 73 | Partially correct | 692 ms | 1768 KB | Output is partially correct |
| 74 | Partially correct | 712 ms | 2060 KB | Output is partially correct |
| 75 | Partially correct | 698 ms | 1760 KB | Output is partially correct |
| 76 | Partially correct | 725 ms | 1360 KB | Output is partially correct |
| 77 | Partially correct | 725 ms | 1800 KB | Output is partially correct |
| 78 | Partially correct | 700 ms | 1880 KB | Output is partially correct |
| 79 | Partially correct | 719 ms | 2036 KB | Output is partially correct |
| 80 | Partially correct | 711 ms | 1844 KB | Output is partially correct |
| 81 | Partially correct | 714 ms | 1744 KB | Output is partially correct |
| 82 | Partially correct | 677 ms | 1324 KB | Output is partially correct |