#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<int>> conn;
vector<int> even, odd;
int make_subtree(int n, unordered_map<int, vector<int>>& tree, bool only_path) {
int dep = 1;
for (int i : conn[n]) {
if (tree.find(i) == tree.end() && none_of(tree[n].begin(), tree[n].end(), [&](int j) { return find(conn[i].begin(), conn[i].end(), j) != conn[i].end(); })) {
tree[n].push_back(i);
tree[i] = vector<int>();
dep = max(dep, make_subtree(i, tree, only_path) + 1);
if (only_path) {
break;
}
}
}
return dep;
}
tuple<int, int, unordered_map<int, vector<int>>, int, int> make_tree() {
pair<int, int> best_dep = {N + 1, N + 1};
unordered_map<int, vector<int>> best_tree;
for (int root = 0; root < N; root++) {
for (int subroot : conn[root]) {
unordered_map<int, vector<int>> tree;
tree[root].push_back(subroot);
tree[subroot] = vector<int>();
int tree_dep = make_subtree(root, tree, false);
int path_dep = make_subtree(subroot, tree, true);
if (tree.size() == N && make_pair(path_dep, tree_dep) < best_dep) {
best_dep = {path_dep, tree_dep};
best_tree = tree;
}
}
}
return make_tuple(0, 0, best_tree, best_dep.second, best_dep.first);
}
vector<int> get_path(int n, int skip, unordered_map<int, vector<int>>& tree) {
for (int i : tree[n]) {
if (i != skip) {
auto path = get_path(i, -1, tree);
path.insert(path.begin(), n);
return path;
}
}
return {n};
}
void gen_moves(int n, int depth, unordered_map<int, vector<int>>& tree) {
if (depth % 2 == 0) even[n] = n;
else odd[n] = n;
for (int i : tree[n]) {
if (depth % 2 == 0) even[i] = n;
else odd[i] = n;
gen_moves(i, depth + 1, tree);
}
}
pair<int, int> end_of_path(int n, int par, unordered_map<int, vector<int>>& tree) {
for (int i : tree[n]) {
return end_of_path(i, n, tree);
}
return {n, par};
}
set<int> get_next(int n, const vector<int>& move) {
set<int> res;
for (int i : conn[n]) {
if (move[i] == move[n]) res.insert(i);
}
if (res.empty()) res.insert(n);
return res;
}
int main() {
cin >> N >> M;
conn.resize(N);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
conn[a].push_back(b);
conn[b].push_back(a);
}
auto [root, subroot, tree, tree_dep, path_dep] = make_tree();
vector<vector<int>> base_moves(2, vector<int>(N));
if (tree_dep + path_dep == N) {
auto path = get_path(subroot, -1, tree);
reverse(path.begin(), path.end());
auto path2 = get_path(root, subroot, tree);
path.insert(path.end(), path2.begin(), path2.end());
even = vector<int>(N);
odd = vector<int>(N);
for (int i = 0; i < N / 2; i++) {
even[path[2 * i]] = even[path[2 * i + 1]];
if (2 * i + 2 < N) odd[path[2 * i + 1]] = even[path[2 * i + 2]];
}
base_moves[0] = even;
base_moves[1] = odd;
} else {
even.resize(N);
odd.resize(N);
gen_moves(root, 0, tree);
gen_moves(subroot, 0, tree);
odd[subroot] = root;
even[subroot] = subroot;
auto [end1, end2] = end_of_path(subroot, root, tree);
odd[end1] = end2;
even[end1] = end2;
base_moves[0] = even;
base_moves[1] = odd;
}
set<pair<int, int>> pos;
for (int a = 0; a < N; a++) {
for (int b = 0; b < a; b++) {
pos.insert({a, b});
}
}
vector<vector<int>> moves;
while (!pos.empty()) {
vector<int> move = base_moves[moves.size() % base_moves.size()];
moves.push_back(move);
set<pair<int, int>> npos;
for (auto [a, b] : pos) {
auto na = get_next(a, move);
auto nb = get_next(b, move);
for (int aa : na) {
for (int bb : nb) {
if (aa != bb && !(aa == b && bb == a)) {
npos.insert({aa, bb});
}
}
}
}
pos = npos;
}
cout << moves.size() << endl;
for (const auto& move : moves) {
for (int i : move) cout << i << ' ';
cout << endl;
}
return 0;
}
Compilation message
Main.cpp: In function 'std::tuple<int, int, std::unordered_map<int, std::vector<int, std::allocator<int> >, std::hash<int>, std::equal_to<int>, std::allocator<std::pair<const int, std::vector<int, std::allocator<int> > > > >, int, int> make_tree()':
Main.cpp:33:29: warning: comparison of integer expressions of different signedness: 'std::unordered_map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
33 | if (tree.size() == N && make_pair(path_dep, tree_dep) < best_dep) {
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
4183 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Execution timed out |
9078 ms |
656976 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
4094 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
4183 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
4183 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
