Submission #1253487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253487		fve5	World Map (IOI25_worldmap)	C++20	72 / 100	113 ms	9540 KiB

worldmap

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

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[A[i] - 1].push_back(B[i] - 1);
        adj[B[i] - 1].push_back(A[i] - 1);
    }

    vector<bool> vis(N);
    vector<int> size(N);
    vector<vector<int>> children(N);
    vector<vector<int>> grid(4 * N, vector<int>(4 * N));

    auto get_size = [&](auto &&get_size, int node) -> int {
        vis[node] = true;
        size[node] = 3;

        for (auto x: adj[node]) {
            if (!vis[x]) {
                size[node] += get_size(get_size, x);
                children[node].push_back(x);
            }
        }
        size[node] += children[node].size();
        return size[node];
    };

    auto dfs = [&](auto &&dfs, int node, int l, int r, int d) -> void {
        for (int i = d; i < 4 * N; i++) {
            for (int j = l; j < r; j++) {
                grid[i][j] = node;
            }
        }
        vis[node] = true;

        int cur_y = 4 * N - 1;
        for (auto x: adj[node]) {
            grid[cur_y][l + 1] = x;
            cur_y -= 2;
        }

        int cur_l = l + 3;
        for (int i = 0; i < children[node].size(); i++) {
            dfs(dfs, children[node][i], cur_l, cur_l + size[children[node][i]], d + 1);
            cur_l += size[children[node][i]] + 1;
        }
    };

    get_size(get_size, 0);
    vis.assign(N, false);
    dfs(dfs, 0, 0, 4 * N, 0);

    for (auto &row: grid)
        for (auto &el: row)
            el++;

    return grid;
}

• 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: 28 / 56