| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 267069 | 2020-08-15T19:01:46 Z | ChrisT | Travelling Salesperson (CCO20_day2problem1) | C++17 | 1422 ms | 24612 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define all(x) (x).begin(),(x).end()
const int MN = 2e3 + 5;
bool adj[MN][MN];
int main () { //REEEEEE IM SO STUPID
int n;
scanf ("%d",&n);
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
char c; scanf (" %c",&c); adj[i][j] = adj[j][i] = c == 'R';
}
}
if (n == 2) return !printf ("2\n1 2\n2\n2 1\n");
if (n == 3) return !printf ("3\n1 2 3\n3\n2 1 3\n3\n3 1 2\n");
for (int st = 1; st <= n; st++) { //idk just go in some order :tm:
int ed = -1;
vector<vector<int>> conn(n+1);
for (int i = 1; i <= n; i++) if (i != st) {
if (~ed) {
if (conn[ed].empty()) {
conn[ed].push_back(i); conn[i].push_back(ed);
continue;
}
if (conn[ed].size() == 1) {
int other = conn[ed][0];
conn[ed].push_back(i); conn[i].push_back(ed);
conn[other].push_back(i); conn[i].push_back(other);
if (adj[i][ed] != adj[i][other]) ed = i;
continue;
}
int del = -1;
for (int j : conn[ed]) if (adj[j][ed] != adj[i][ed]) {
del = j;
break;
}
if (del == -1) del = conn[ed][0];
conn[ed].erase(find(all(conn[ed]),del));
conn[del].erase(find(all(conn[del]),ed));
conn[ed].push_back(i); conn[i].push_back(ed);
conn[del].push_back(i); conn[i].push_back(del);
if (adj[i][del] == adj[i][ed]) ed = del;
else ed = i;
} else ed = i;
}
vector<int> path = {st,ed};
int cur = adj[ed][conn[ed][0]] == adj[st][ed] ? conn[ed][0] : conn[ed][1], lst = ed;
while (cur != ed) {
path.push_back(cur); int nxt = -1;
for (int i : conn[cur]) if (i != lst) nxt = i;
lst = cur;
cur = nxt;
}
printf ("%lu\n",path.size());
for (int i : path) printf ("%d ",i);
printf ("\n");
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 384 KB | Output is correct |
| 2 | Correct | 1 ms | 384 KB | Output is correct |
| 3 | Correct | 1 ms | 384 KB | Output is correct |
| 4 | Correct | 1 ms | 384 KB | Output is correct |
| 5 | Correct | 1 ms | 384 KB | Output is correct |
| 6 | Correct | 1 ms | 384 KB | Output is correct |
| 7 | Correct | 1 ms | 384 KB | Output is correct |
| 8 | Correct | 1 ms | 384 KB | Output is correct |
| 9 | Correct | 1 ms | 384 KB | Output is correct |
| 10 | Correct | 1 ms | 384 KB | Output is correct |
| 11 | Correct | 1 ms | 384 KB | Output is correct |
| 12 | Correct | 1 ms | 384 KB | Output is correct |
| 13 | Correct | 1 ms | 384 KB | Output is correct |
| 14 | Correct | 1 ms | 384 KB | Output is correct |
| 15 | Correct | 1 ms | 384 KB | Output is correct |
| 16 | Correct | 1259 ms | 24056 KB | Output is correct |
| 17 | Correct | 1298 ms | 24204 KB | Output is correct |
| 18 | Correct | 1 ms | 384 KB | Output is correct |
| 19 | Correct | 1306 ms | 24112 KB | Output is correct |
| 20 | Correct | 1283 ms | 24260 KB | Output is correct |
| 21 | Correct | 1 ms | 384 KB | Output is correct |
| 22 | Correct | 1249 ms | 24184 KB | Output is correct |
| 23 | Correct | 1225 ms | 24056 KB | Output is correct |
| 24 | Correct | 4 ms | 616 KB | Output is correct |
| 25 | Correct | 1226 ms | 24032 KB | Output is correct |
| 26 | Correct | 1228 ms | 24312 KB | Output is correct |
| 27 | Correct | 84 ms | 2424 KB | Output is correct |
| 28 | Correct | 1286 ms | 24220 KB | Output is correct |
| 29 | Correct | 1277 ms | 24184 KB | Output is correct |
| 30 | Correct | 1283 ms | 24100 KB | Output is correct |
| 31 | Correct | 1289 ms | 24056 KB | Output is correct |
| 32 | Correct | 1359 ms | 24108 KB | Output is correct |
| 33 | Correct | 1396 ms | 24232 KB | Output is correct |
| 34 | Correct | 1377 ms | 24108 KB | Output is correct |
| 35 | Correct | 1257 ms | 24188 KB | Output is correct |
| 36 | Correct | 1283 ms | 24248 KB | Output is correct |
| 37 | Correct | 1256 ms | 24060 KB | Output is correct |
| 38 | Correct | 1422 ms | 24056 KB | Output is correct |
| 39 | Correct | 1255 ms | 23996 KB | Output is correct |
| 40 | Correct | 1324 ms | 24184 KB | Output is correct |
| 41 | Correct | 1287 ms | 24056 KB | Output is correct |
| 42 | Correct | 1264 ms | 24016 KB | Output is correct |
| 43 | Correct | 1237 ms | 24316 KB | Output is correct |
| 44 | Correct | 1353 ms | 24152 KB | Output is correct |
| 45 | Correct | 1246 ms | 24172 KB | Output is correct |
| 46 | Correct | 1247 ms | 24056 KB | Output is correct |
| 47 | Correct | 1212 ms | 24232 KB | Output is correct |
| 48 | Correct | 1312 ms | 24064 KB | Output is correct |
| 49 | Correct | 1338 ms | 24244 KB | Output is correct |
| 50 | Correct | 1301 ms | 24072 KB | Output is correct |
| 51 | Correct | 1231 ms | 24056 KB | Output is correct |
| 52 | Correct | 1202 ms | 24360 KB | Output is correct |
| 53 | Correct | 1271 ms | 24132 KB | Output is correct |
| 54 | Correct | 1270 ms | 24256 KB | Output is correct |
| 55 | Correct | 1235 ms | 24184 KB | Output is correct |
| 56 | Correct | 1234 ms | 24236 KB | Output is correct |
| 57 | Correct | 1213 ms | 24220 KB | Output is correct |
| 58 | Correct | 1229 ms | 24252 KB | Output is correct |
| 59 | Correct | 1257 ms | 24312 KB | Output is correct |
| 60 | Correct | 1201 ms | 24248 KB | Output is correct |
| 61 | Correct | 1215 ms | 24276 KB | Output is correct |
| 62 | Correct | 1259 ms | 24152 KB | Output is correct |
| 63 | Correct | 1341 ms | 24200 KB | Output is correct |
| 64 | Correct | 1230 ms | 24244 KB | Output is correct |
| 65 | Correct | 1275 ms | 24344 KB | Output is correct |
| 66 | Correct | 1187 ms | 24264 KB | Output is correct |
| 67 | Correct | 1280 ms | 24248 KB | Output is correct |
| 68 | Correct | 1272 ms | 24220 KB | Output is correct |
| 69 | Correct | 1308 ms | 24180 KB | Output is correct |
| 70 | Correct | 1279 ms | 24312 KB | Output is correct |
| 71 | Correct | 1271 ms | 24200 KB | Output is correct |
| 72 | Correct | 1350 ms | 24128 KB | Output is correct |
| 73 | Correct | 1199 ms | 24244 KB | Output is correct |
| 74 | Correct | 1209 ms | 24188 KB | Output is correct |
| 75 | Correct | 1220 ms | 24184 KB | Output is correct |
| 76 | Correct | 1209 ms | 24244 KB | Output is correct |
| 77 | Correct | 1219 ms | 24184 KB | Output is correct |
| 78 | Correct | 1223 ms | 24184 KB | Output is correct |
| 79 | Correct | 1181 ms | 24184 KB | Output is correct |
| 80 | Correct | 1232 ms | 24220 KB | Output is correct |
| 81 | Correct | 1218 ms | 24176 KB | Output is correct |
| 82 | Correct | 1215 ms | 24168 KB | Output is correct |
| 83 | Correct | 1229 ms | 24424 KB | Output is correct |
| 84 | Correct | 1286 ms | 24128 KB | Output is correct |
| 85 | Correct | 1265 ms | 24192 KB | Output is correct |
| 86 | Correct | 1264 ms | 24272 KB | Output is correct |
| 87 | Correct | 73 ms | 2424 KB | Output is correct |
| 88 | Correct | 72 ms | 2424 KB | Output is correct |
| 89 | Correct | 1226 ms | 24308 KB | Output is correct |
| 90 | Correct | 1249 ms | 24440 KB | Output is correct |
| 91 | Correct | 78 ms | 2424 KB | Output is correct |
| 92 | Correct | 84 ms | 2428 KB | Output is correct |
| 93 | Correct | 1237 ms | 24368 KB | Output is correct |
| 94 | Correct | 1228 ms | 24612 KB | Output is correct |
| 95 | Correct | 72 ms | 2424 KB | Output is correct |
| 96 | Correct | 74 ms | 2424 KB | Output is correct |
| 97 | Correct | 1216 ms | 24144 KB | Output is correct |
| 98 | Correct | 1357 ms | 24216 KB | Output is correct |