Submission #1253478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253478		fve5	World Map (IOI25_worldmap)	C++20	15 / 100	60 ms	7496 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>> grid(4 * N, vector<int>(4 * N));

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

        int children = 0;
        for (auto x: adj[node]) {
            if (!vis[x]) {
                size[node] += get_size(get_size, x);
                children++;
            }
        }
        size[node] += children;
        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;

        vector<int> children;
        for (auto x: adj[node])
            if (!vis[x])
                children.push_back(x);

        int cur_l = l + 3;
        for (int i = 0; i < children.size(); i++) {
            dfs(dfs, children[i], cur_l, cur_l + size[children[i]], d + 1);
            cur_l += size[children[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: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56