oj.uz

Submission #1065297

# Submission time Handle Problem Language Result Execution time Memory
1065297 2024-08-19T06:06:03 Z PurpleCrayon Make them Meet (EGOI24_makethemmeet) C++17
53.7365 / 100
 7 ms 980 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> og[N];
vector<int> adj[N];
vector<vector<int>> ans;
int par[N];

bool vis[N];
void dfs_build_tree(int c, int p) {
    vis[c] = 1;
    if (p != -1) {
        // cerr << c << ' ' << p << endl;
        adj[p].push_back(c), adj[c].push_back(p);
    }

    for (int nxt : og[c]) if (!vis[nxt]) {
        dfs_build_tree(nxt, c);
    }
}

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;
    }

    srand(time(0));
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        og[a].push_back(b), og[b].push_back(a);
        /*
        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_build_tree(0, -1);
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 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 Incorrect 0 ms 348 KB If people start at 0 and 1, then they can avoid each other
3 Halted 0 ms 0 KB -

Subtask #3
10.3451314329 / 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 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Partially correct 4 ms 864 KB Partially correct
6 Partially correct 5 ms 860 KB Partially correct
7 Correct 2 ms 604 KB Output is correct

Subtask #4
33.3913423068 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 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 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Partially correct 4 ms 864 KB Partially correct
11 Partially correct 5 ms 860 KB Partially correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Partially correct 5 ms 860 KB Partially correct
22 Partially correct 4 ms 860 KB Partially correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Partially correct 5 ms 928 KB Partially correct
28 Partially correct 5 ms 860 KB Partially correct
29 Partially correct 5 ms 860 KB Partially correct
30 Partially correct 5 ms 860 KB Partially correct
31 Partially correct 5 ms 860 KB Partially correct
32 Partially correct 4 ms 860 KB Partially correct
33 Partially correct 6 ms 856 KB Partially correct
34 Partially correct 4 ms 860 KB Partially correct
35 Partially correct 5 ms 856 KB Partially correct
36 Partially correct 5 ms 860 KB Partially correct
37 Partially correct 4 ms 924 KB Partially correct
38 Partially correct 4 ms 908 KB Partially correct
39 Partially correct 7 ms 856 KB Partially correct
40 Partially correct 4 ms 856 KB Partially correct
41 Partially correct 5 ms 860 KB Partially correct
42 Partially correct 5 ms 860 KB Partially correct
43 Partially correct 5 ms 860 KB Partially correct
44 Partially correct 4 ms 980 KB Partially correct
45 Partially correct 5 ms 860 KB Partially correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 344 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 344 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB If people start at 0 and 1, then they can avoid each other
8 Halted 0 ms 0 KB -