| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 846572 | math_rabbit_1028 | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
vector<int> longest_trip(int N, int D) {
int n = N;
vector<int> adj[256];
vector<int> res;
res.clear();
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
int ch[256]; for (int i = 0; i < n; i++) ch[i] = 0;
vector<int> path, clique;
path.push_back(0);
ch[0] = 1;
while (true) {
int bef = path.size();
for (int i = 0; i < adj[path.back()].size(); i++) {
int v = adj[path.back()][i];
if (ch[v] == 0) {
ch[v] = 1;
path.push_back(v);
break;
}
}
if (bef == path.size()) break;
}
for (int i = 0; i < n; i++) if (ch[i] == 0) clique.push_back(i);
bool connected = false;
for (int i = 0; i < path.size(); i++) {
for (int j = 0; j < adj[path[i]].size(); j++) {
if (ch[adj[path[i]][j]] == 0) connected = true;
}
}
if (connected) {
for (int i = 0; i < adj[path[0]].size(); i++) {
if (ch[adj[path[0]][i]] == 0) {
int target = ch[adj[path[0]][i]];
res = path;
reverse(res.begin(), res.end());
int t = 0;
for (t = 0; t < clique.size(); j++) if (clique[t] == target) break;
swap(clique[0], clique[t]);
for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
return res;
}
}
int s = path.size() - 1;
for (int i = 0; i < adj[s].size(); i++) {
if (ch[adj[s][i]] == 0) {
int target = ch[adj[s][i]];
res = path;
int t = 0;
for (t = 0; t < clique.size(); j++) if (clique[t] == target) break;
swap(clique[0], clique[t]);
for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
return res;
}
}
for (int i = 0; i < clique.size(); i++) {
for (int j = 0; j < adj[clique[i]].size(); j++) {
if (ch[adj[clique[i]][j]] == 1) {
int target = adj[clique[i]][j];
swap(clique[i], clique.back());
res = clique;
while (path[0] != target) {
int front = path[0];
path.erase(path.begin());
path.push_back(front);
}
for (int k = 0; k < path.size(); k++) res.push_back(path[k]);
return res;
}
}
}
}
else {
if (path.size() > clique.size()) return path;
return clique;
}
return {}; // never reached
}