Submission #1256527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256527		kargneq	World Map (IOI25_worldmap)	C++20	72 / 100	75 ms	9544 KiB

worldmap

#include "worldmap.h"
using namespace std;

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {

    int K = 4*N;
    vector grid(K, vector<int>(K, 1));
    
    vector<int> order;
    vector<vector<int>> ad(N+1);

    for(int i=0; i<M; i++) {
        ad[A[i]].push_back(B[i]);
        ad[B[i]].push_back(A[i]);
    }

    vector<int> vis(N+1);

    auto dfs = [&](auto &&self, int v) -> void {
        vis[v] = 1;

        order.push_back(v);

        for(int u: ad[v]) {
            if(!vis[u]) {
                self(self, u);
                order.push_back(N + v);
            }
        }

    };

    dfs(dfs, 1);

    int curr_col = 0;

    for(int v: order) {
        if(v <= N) {
            for(int i=0; i<K; i++) {
                for(int j=curr_col; j < curr_col + 3; j++) {
                    grid[i][j] = v;
                }
            }

            for(int i=0; i<ad[v].size(); i++) {
                grid[2*i][curr_col + 1] = ad[v][i];
                grid[2*i + 1][curr_col+1] = v;
            }
            curr_col += 3;
        }
        else {
            for(int i=0; i<K; i++) {
                grid[i][curr_col] = v - N;
            }
            curr_col++;
        }
    }

    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