Submission #1256210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256210		sonlh07	World Map (IOI25_worldmap)	C++20	44 / 100	56 ms	6980 KiB

worldmap

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pp pair<int, int>
#define ppp pair<pp, int>
#define pp4 pair<pp, pp>
#define pp3 pair<ll, pair<int, int> > 
#define mat vector<vector<int>>
#define fi first
#define se second
#define mod 1000000007
#define inf 2000000001
#define esp 1e-9
#define BLOCK 333
#define BITNUM 555
#define BASE 180518
typedef long long ll;
// const ll oo = (ll)1e18 + 1;
using namespace std;

mat concat_cols(const std::vector<mat>& childs, int parent) {
    int mx = 0;
    for (const auto& ch : childs) {
        mx = std::max(mx, (int)ch.size());
    }
    mat ans;
    for (int i = 0; i < mx; i++) {
        std::vector<int> row;
        for (const auto& ch : childs) {
            int ncols = ch.empty() ? 0 : (int)ch[0].size();
            row.push_back(parent);
            for (int j = 0; j < ncols; j++) {
                if (i >= (int)ch.size()) row.push_back(parent);
                else row.push_back(ch[i][j]);
            }
        }
        row.push_back(parent);
        ans.push_back(std::move(row));
    }
    return ans;
}

mat concat_rows(const vector<mat>& childs, int parent) {
    int mx = 0;
    for (const auto &ch: childs) {
        mx = max(mx, (int) ch[0].size());
    }

    mat ans;
    for (const auto& ch : childs) {
        for (auto row: ch) {
            vector<int> concat_row = row;
            while ((int) concat_row.size() < mx) {
                concat_row.push_back(parent); 
            }
            ans.push_back(std::move(concat_row));
        }
    }
    return ans;
}

set<int> generated;

vector<vector<int>> generate(int parent, vector<vector<int>> &adj, ll mask) {
    if (generated.count(parent)) {
        return {{parent}};
    }
    generated.insert(parent);
    vector<int> childs;
    for (int c: adj[parent]) {
        // not visited
        if (!((mask >> c) & 1)) {
            childs.push_back(c);
        }
    }
    // no childs
    if (childs.size() == 0) {
        return {{parent}};
    }

    vector<mat> child_maps;
    // cout << "Parent == " << parent << "\n";
    for (int c: childs) {
        auto child_map = generate(c, adj, mask | (1ll << parent));
        // cout << "=== map ===\n";
        // for (auto ch: child_map) {
        //     for (auto c: ch) cout << c << " ";
        //     cout << "\n";
        // }
        child_maps.push_back(child_map);
    }

    sort(child_maps.begin(), child_maps.end(), [&](auto c1, auto c2){
        return c1[0].size() > c2[0].size();
    });

    // zip them
    int m = (int) child_maps.size();
    int w = max(1, (int) sqrt(m));
    
    vector<mat> rows;
    for (int i = 0; i < m; i += w) {
        int l = i;
        int r = min(m - 1, i + w - 1);
        vector<mat> subs;
        for (int j = l; j <= r; j++) subs.push_back(child_maps[j]);
        mat center = concat_cols(subs, parent);
        int col = (int)center[0].size();
        mat ret;
        vector<int> last_row(col, parent);
        ret.push_back(std::move(last_row));
        for (auto r: center) ret.push_back(r);
        ret.push_back(std::move(last_row));
        rows.push_back(ret);
    }
    return concat_rows(rows, parent);
}

mat create_full_map(int N, mat &adj) {
    int mx = N + N;
    mat ret(mx, vector<int>(mx, 0));

    for (int i = 0; i < N; i++) {
        int idx = 0;
        for (auto c: adj[i]) {
            ret[i][idx] = i;
            ret[i][idx + 1] = c;
            idx += 2;
        }
    }

    for (int i = 0; i < mx; i++)
        for (int j = 0; j < mx; j++)
            ret[i][j]++;
    return ret;
}

mat create_one_map(int N, vector<pp> edge) {
    int idx = 0;
    int m = edge.size();
    vector<vector<int>> ret(4 * N, vector<int>(4 * N, 0));
    for (int i = 0; i < N; i++) {
        if (idx >= m) break;
        int st = (i & 1) ? 0 : 2;
        for (int j = 0; j < N; j++) {
            if (idx >= m) break;
            ret[i][st] = edge[idx].first;
            ret[i][st + 1] = edge[idx].second;
            idx++;
            st += 4;
        }
    }
    for (int i = 0; i < 4 * N; i++)
        for (int j = 0; j < 4 * N; j++)
            ret[i][j]++;

    return ret;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    generated.clear();
    vector<vector<int>> adj(N, vector<int>());
    for (int i = 0; i < M; i++) {
        int u = A[i], v = B[i];
        u--;
        v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    
    if (M == N * (N - 1) / 2) {
        return create_full_map(N, adj);
    }

    if (adj[0].size() == N - 1) {
        vector<pp> edge;
        for (int i = 0; i < M; i++) edge.push_back({A[i] - 1, B[i] - 1});
        return create_one_map(N, edge);
    }

    // detect best root
    vector<bool> visited(N, false);

    function<int(int, int)> dfs = [&](int u, int deep) {
        visited[u] = true;
        int ret = deep;
        for (int v: adj[u]) {
            if (!visited[v]) {
                ret = max(ret, dfs(v, deep + 1));
            }
        }
        return ret;
    };

    int root = 0, mdeep = inf;
    for (int i = 0; i < N; i++) {
        visited.assign(N, false);
        int ret = dfs(i, 0);
        if (mdeep > ret) {
            root = i;
            mdeep = ret;
        }
    }

    auto rec_map = generate(root, adj, (1ll << root));
    int h = rec_map.size();
    int w = rec_map[0].size();
    int mx = max(h, w);

    vector<vector<int>> ret(mx, vector<int>(mx, root));

    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            ret[i][j] = rec_map[i][j];

    for (int i = 0; i < mx; i++)
        for (int j = 0; j < mx; j++)
            ret[i][j]++;

    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 0 / 56