Submission #1065295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065295		PurpleCrayon	Make them Meet (EGOI24_makethemmeet)	C++17	53.74 / 100	6 ms	980 KiB

Main

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e2+10, MOD = 1e9+7;
const ll INF = 1e18+10;

int n, m;
int col[N];
vector<int> adj[N];
vector<vector<int>> ans;
int par[N];

void dfs_col(int c, int p) {
    // cerr << "> " << c << ' ' << col[c] << endl;
    par[c] = p;
    for (int nxt : adj[c]) if (nxt != p) {
        col[nxt] = col[c] ^ 1;
        dfs_col(nxt, c);
    }
}


void dfs_par(int c, int p) {
    par[c] = p;
    for (int nxt : adj[c]) if (nxt != p)
        dfs_par(nxt, c);
}

int swim(int b) {
    // cerr << "swim(" << b << ")\n";
    int cur_good = 0, my_good = -1;
    for (int i = 0; i < n; i++) if (col[i] == b) cur_good++, my_good = i;
    if (cur_good <= 1)
        return my_good;

    auto dead = [&](int c) {
        return sz(adj[c]) == 1 && col[c] != b;
    };

    auto alive_leaf = [&](int c) {
        if (col[c] != b) return false;
        int cnt = 0;
        for (int nxt : adj[c])
            cnt += !dead(nxt);

        assert(cnt);
        return cnt == 1;
    };

    int root = -1;
    for (int i = 0; i < n; i++) if (col[i] == b) {
        if (alive_leaf(i)) {
            root = i;
            break;
        }
    }

    int root_child = -1;
    for (int nxt : adj[root]) {
        if (!dead(nxt)) {
            root_child = nxt;
        }
    }

    assert(root != -1 && root_child != -1);
    dfs_par(root, -1);

    int ops = 2 * n;
    for (int rep = 0; rep < ops; rep++) {
        if (rep % 2 == 0) { // move from b to ~b
            vector<int> v(n, -1);
            int cc = 1;
            for (int i = 0; i < n; i++) if (col[i] != b && !dead(i)) {
                v[i] = cc++;
            }

            v[root] = v[root_child];
            for (int i = 0; i < n; i++) if (col[i] == b && i != root) {
                v[i] = v[par[i]];
            }

            for (int i = 0; i < n; i++) if (v[i] == -1)
                v[i] = cc++;

            ans.push_back(v);
        } else { // move from ~b to b
            vector<int> v(n, -1);
            int cc = 1;
            for (int i = 0; i < n; i++) if (col[i] == b) {
                v[i] = cc++;
            }

            for (int i = 0; i < n; i++) if (col[i] != b && !dead(i)) {
                v[i] = v[par[i]];
            }

            for (int i = 0; i < n; i++) if (v[i] == -1)
                v[i] = cc++;

            ans.push_back(v);
        }
    }

    // cerr << "swim to: " << root << " with " << sz(ans) << '\n';

    return root;
}

vector<int> get_path(int a, int b) {
    dfs_par(b, -1);
    vector<int> path;
    while (true) {
        path.push_back(a);
        if (a == b) break;
        a = par[a];
    }
    return path;
}

void check() {
    vector<pair<int, int>> opts;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            opts.emplace_back(i, j);

    for (auto v : ans) {
        vector<pair<int, int>> new_opts;
        // cerr << "start layer\n";
        for (auto [a, b] : opts) {
            vector<int> cana, canb;
            for (int na : adj[a]) if (v[a] == v[na]) {
                cana.push_back(na);
            }
            if (sz(cana) == 0) cana.push_back(a);
            for (int nb : adj[b]) if (v[b] == v[nb]) {
                canb.push_back(nb);
            }
            if (sz(canb) == 0) canb.push_back(b);

            for (int x : cana) {
                for (int y : canb) {
                    if (x != b && y != a && x != y) {
                        // cerr << "from: (" << a << ", " << b << ") to: (" << x << ", " << y << ")\n";
                        new_opts.emplace_back(min(x, y), max(x, y));
                    }
                }
            }
        }

        sort(new_opts.begin(), new_opts.end());
        new_opts.resize(unique(new_opts.begin(), new_opts.end()) - new_opts.begin());
        swap(opts, new_opts);
    }

    assert(sz(opts) == 0);
}

void solve() {
    /*
    n = rand() % 20 + 2;
    m = n - 1;
    */
    cin >> n >> m;
    if (n == 2) {
        cout << "1\n1 1\n";
        return;
    }

    assert(m == n-1);
    srand(time(0));
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        /*
        int a = i, b = i + 1;
        int a = i + 1, b = rand() % (i + 1);
        */
        // cerr << "input: " << a << ' ' << b << endl;
        adj[a].push_back(b), adj[b].push_back(a);
    }


    dfs_col(0, -1);
    /*
    for (int i = 0; i < n; i++)
        cerr << col[i] << ' ';
    cerr << endl;
    */

    int a = -1, b = -1;
    for (int i = 0; i < n; i++) if (sz(adj[i]) == 1) { // the problem is, something on the color can switch sides after going to the wrong one
        a = swim(col[i]);
        b = swim(col[i] ^ 1);
        a = swim(col[i]);
        b = swim(col[i] ^ 1);
        break;
    }


    auto path = get_path(a, b);
    for (int i = 1; i < sz(path); i++) {
        int x = path[i-1];
        int y = path[i];
        vector<int> v(n, 1);
        v[x] = 2, v[y] = 2;
        ans.push_back(v);
    }

    cout << sz(ans) << '\n';
    for (auto v : ans) {
        for (int x : v) cout << x << ' ';
        cout << '\n';
    }
    cout.flush();

#ifdef LOCAL
    check();
#endif
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}


// general idea: two-color the tree, assume that white is more common
// we can cancel out all white nodes by swimming them up to the root:
//      - root the tree at a leaf
//      - keep swimming the nodes up (make sure that the root swims down to maintain the colors its on)
//
// per turn:
//      ~ n ops to bring things to the top (make sure its even)
//
//
//
// if there's both a white and black leaf:
//      pull the white things towards the white leaf (n queries)
//      pull the black things towards the black leaf (n queries)
//      make them touch by bringing them together
// otherwise:
//      
//

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