oj.uz

Submission #1065218

# Submission time Handle Problem Language Result Execution time Memory
1065218 2024-08-19T03:37:23 Z PurpleCrayon Make them Meet (EGOI24_makethemmeet) C++17
21 / 100
 3 ms 872 KB 
#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;
    };

    int root = -1;
    for (int i = 0; i < n; i++) if (col[i] == b) {
        int cnt = 0;
        for (int nxt : adj[i]) {
            cnt += !dead(nxt);
        }
        assert(cnt);
        if (cnt == 1) {
            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 = n + (n % 2);
    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() {
    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;
        */
        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) {
        a = swim(col[i]);
        a = swim(col[i]);
        b = swim(col[i] ^ 1);
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 668 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #4
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 668 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 0 ms 464 KB Output is correct
19 Correct 0 ms 360 KB Output is correct
20 Correct 1 ms 360 KB Output is correct
21 Correct 2 ms 616 KB Output is correct
22 Correct 3 ms 872 KB Output is correct
23 Correct 1 ms 360 KB Output is correct
24 Incorrect 1 ms 360 KB If people start at 1 and 3, then they can avoid each other
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 1 ms 604 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -