Submission #1098570

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

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<vector<int>> adj(n, vector<int>(n, 0));
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        if (x == y || adj[x][y]) continue;
        g[x].push_back(y);
        g[y].push_back(x);
        adj[x][y] = adj[y][x] = 1;
    }

    if (!count_if(g.begin(), g.end(), [&](const vector<int>& v) { return v.size() < n - 1; })) {
        int q = n + (n % 2);
        vector<int> circ(q), col(q, 0);
        iota(circ.begin(), circ.end(), 0);
        cout << 2 * (q - 1) << endl;
        for (int _ = 0; _ < q - 1; _++) {
            for (int i = 0; i < q / 2; i++) {
                col[circ[i]] = col[circ[q - 1 - i]] = i;
            }
            for (int i = 0; i < n; i++) cout << col[i] << ' ';
            cout << endl;
            for (int i = 0; i < n; i++) cout << col[i] << ' ';
            cout << endl;
            rotate(circ.begin() + 1, circ.begin() + 2, circ.end());
        }
        return 0;
    }

    auto go = [&]() {
        for (int r = 0; r < n; r++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (r != x && r != y && x != y) {
                        if (adj[r][x] == 1 && adj[r][y] == 1 && adj[x][y] == 0) {
                            g[r].insert(g[r].begin(), {x, y});
                            return r;
                        }
                    }
                }
            }
        }
        return -1;
    };

    int root = go();
    assert(root != -1);

    vector<vector<int>> childs(n);
    vector<int> par(n, -1);
    par[root] = -2;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int y : g[x]) {
            if (par[y] == -1) {
                childs[x].push_back(y);
                par[y] = x;
                q.push(y);
            }
        }
    }

    for (int x : childs[root]) {
        vector<int> bad;
        for (int y : childs[root]) {
            if (adj[x][y]) bad.push_back(y);
        }
        for (int y : bad) {
            childs[root].erase(remove(childs[root].begin(), childs[root].end(), y), childs[root].end());
            childs[x].push_back(y);
            par[y] = x;
        }
    }

    vector<vector<int>> ans;
    vector<int> free(n, 0);
    free[root] = 1;
    
    while (accumulate(free.begin(), free.end(), 0) < n - 1) {
        vector<int> col(n), active(free), nfree(free);
        iota(col.begin(), col.end(), 1);

        if (!free[root]) {
            int best = 1e9, b = -1;
            for (int x : childs[root]) {
                int pending = count_if(childs[x].begin(), childs[x].end(), [&](int y) { return !free[y]; });
                if (free[x] && pending < best) {
                    best = pending;
                    b = x;
                }
            }
            active[b] = 0;
            col[b] = col[root];
            nfree[b] = 0;
            nfree[root] = 1;
        } else {
            active[root] = 1e9;
        }

        for (int x = 0; x < n; x++) {
            if (x != root && !free[x] && active[par[x]] >= 1) {
                col[x] = col[par[x]];
                active[par[x]]--;
                nfree[x] = 1;
                nfree[par[x]] = 0;
            }
        }

        ans.push_back(col);
        free = nfree;
    }

    assert(!free[root]);

    function<void(int)> dfs = [&](int x) {
        for (int y : childs[x]) {
            vector<int> col(n);
            iota(col.begin(), col.end(), 1);
            col[y] = col[x];
            ans.push_back(col);
            dfs(y);
            ans.push_back(col);
        }
    };
    
    dfs(root);

    cout << ans.size() << endl;
    for (const auto& col : ans) {
        for (int c : col) cout << c << ' ';
        cout << endl;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:19:83: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |     if (!count_if(g.begin(), g.end(), [&](const vector<int>& v) { return v.size() < n - 1; })) {
      |                                                                          ~~~~~~~~~^~~~~~~

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