#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) {
add(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
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:28:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
28 | while (ans.size() + 2 <= N) {
| ~~~~~~~~~~~~~~~^~~~
longesttrip.cpp:54:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | if (ans.size() == N - 1) {
| ~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
20 ms |
600 KB |
Output is correct |
| 3 |
Correct |
115 ms |
600 KB |
Output is correct |
| 4 |
Correct |
352 ms |
1124 KB |
Output is correct |
| 5 |
Correct |
720 ms |
1792 KB |
Output is correct |
| 6 |
Correct |
7 ms |
344 KB |
Output is correct |
| 7 |
Correct |
22 ms |
344 KB |
Output is correct |
| 8 |
Correct |
121 ms |
856 KB |
Output is correct |
| 9 |
Correct |
268 ms |
1364 KB |
Output is correct |
| 10 |
Correct |
673 ms |
1736 KB |
Output is correct |
| 11 |
Correct |
705 ms |
1884 KB |
Output is correct |
| 12 |
Correct |
689 ms |
1656 KB |
Output is correct |
| 13 |
Correct |
654 ms |
1576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
