Submission #1098563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098563		Trisanu_Das	Make them Meet (EGOI24_makethemmeet)	C++17	0 / 100	9102 ms	1048576 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

int N, M;
map<int, vector<int>> conn;

int make_subtree(int n, 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] = {};
            dep = max(dep, make_subtree(i, tree, only_path) + 1);
            if (only_path) break;
        }
    }
    return dep;
}

tuple<int, int, map<int, vector<int>>, int, int> make_tree() {
    pair<int, int> best_dep = {N+1, N+1};
    tuple<int, int, map<int, vector<int>>, int, int> best_tree;
    for (int root = 0; root < N; ++root) {
        for (int subroot : conn[root]) {
            map<int, vector<int>> tree;
            tree[root] = {subroot};
            tree[subroot] = {};
            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 = {root, subroot, tree, tree_dep, path_dep};
            }
        }
    }
    return best_tree;
}

vector<int> get_path(int n, map<int, vector<int>>& tree, int skip) {
    for (int i : tree[n]) {
        if (i != skip) {
            vector<int> result = get_path(i, tree, -1);
            result.insert(result.begin(), n);
            return result;
        }
    }
    return {n};
}

set<int> get_next(int n, 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;
    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<int> even(N), odd(N), path;
    vector<vector<int>> base_moves;

    if (tree_dep + path_dep == N) {
        vector<int> p1 = get_path(subroot, tree, -1);
        vector<int> p2 = get_path(root, tree, subroot);
        reverse(p1.begin(), p1.end());
        path = p1;
        path.insert(path.end(), p2.begin(), p2.end());

        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 = {even, odd};
    } else {
        even = vector<int>(N);
        odd = vector<int>(N);

        function<void(int, int)> gen_moves = [&](int n, int depth) {
            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);
            }
        };

        gen_moves(root, 0);
        gen_moves(subroot, 0);
        odd[subroot] = root;
        even[subroot] = subroot;

        function<pair<int, int>(int, int)> end_of_path = [&](int n, int par) {
            for (int i : tree[n]) {
                return end_of_path(i, n);
            }
            return make_pair(n, par);
        };

        auto [end1, end2] = end_of_path(subroot, root);
        odd[end1] = end2;
        even[end1] = end2;

        base_moves = {even, 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) {
            set<int> na = get_next(a, move);
            set<int> 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 (stderr)

Main.cpp: In function 'std::tuple<int, int, std::map<int, std::vector<int, std::allocator<int> >, std::less<int>, std::allocator<std::pair<const int, std::vector<int, std::allocator<int> > > > >, int, int> make_tree()':
Main.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             if (tree.size() == N && make_pair(path_dep, tree_dep) < best_dep) {
      |                 ~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 11
• Subtask 4: 0 / 36
• Subtask 5: 0 / 30