Submission #1270465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270465		feining_for_gm	World Map (IOI25_worldmap)	C++20	100 / 100	26 ms	2860 KiB

worldmap

#pragma GCC optimize("O3")
//#include "worldmap.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;

const long long INF = 100000000000000;

std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
    std::vector<std::vector<int>> adj(n+1);
    for(int i = 0; i < m; ++i) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    int mdepth = 0;
    std::vector<int> order, visited(n+1, 0), layer(n+1, 0), par(n+1, 0), tin(n+1, 0), tout(n+1, 0);
    auto dfs = [&](int u, int p, auto &&dfs) -> void {
        order.push_back(u);
        tin[u] = order.size()-1;
        layer[u] = layer[p]+1;
        mdepth = std::max(mdepth, layer[u]);
        par[u] = p;
        int cnt = 0;
        for(auto v : adj[u]) cnt += !visited[v];
        if(!cnt) {
            tout[u] = order.size()-1;
            visited[u] = 1;
            return;
        }

        visited[u] = 1;
        for(auto v : adj[u]) {
            if(v == p || visited[v]) continue;
            dfs(v, u, dfs);
            order.push_back(u);
        }

        tout[u] = order.size()-1;
    };

    layer[1] = 1;
    dfs(1, 0, dfs);

    std::vector<int> start(n+1, 0);
    for(int i = 1; i <= n; ++i) start[i] = tin[i]+2;

    std::vector<std::vector<int>> matrix(2*n, std::vector<int>(2*n, -1));
    /*
    while(mdepth) {
        for(int i = 0; i < 3; ++i) matrix.push_back(order);
        for(int i = 0; i < order.size(); ++i) {
            if(layer[order[i]] == mdepth) order[i] = par[order[i]];
        }

        --mdepth;
    }*/
    for(int i = 0; i < order.size(); ++i) matrix[2*n-1][i] = order[i];
    for(int i = 0; i < order.size(); ++i) {
        if(layer[order[i]] == mdepth) order[i] = par[order[i]];
    }
    --mdepth;
    int crow = 2*n-2;
    while(mdepth) {
        for(int i = 0; i < order.size(); ++i) {
            if(layer[order[i]] == mdepth) {
                if(i > tin[order[i]] && i < tout[order[i]]) matrix[crow][i] = order[i];
                else matrix[crow][i] = par[order[i]];
            } else {
                matrix[crow][i] = order[i];
            }
        }

        --crow;
        for(int i = 0; i < order.size(); ++i) {
            if(layer[order[i]] == mdepth) {
                if((tin[order[i]]%2) == (i%2)) matrix[crow][i] = order[i];
                else matrix[crow][i] = par[order[i]];
            } else {
                matrix[crow][i] = order[i];
            }
        }
        --crow;

        for(int i = 0; i < order.size(); ++i) {
            if(layer[order[i]] == mdepth) order[i] = par[order[i]];
        }
        --mdepth;
    }

    for(int i = 0; i < 2*n; ++i) {
        for(int j = 0; j < 2*n; ++j) {
            if(matrix[i][j] == -1 || matrix[i][j] == 0) matrix[i][j] = 1;
        }
    }

    //std::reverse(matrix.begin(), matrix.end());

    std::set<std::array<int, 2>> edges;
    for(int i = 1; i <= n; ++i) {
        for(auto j : adj[i]) {
            if(layer[i] < layer[j]) edges.insert({i, j});
            else edges.insert({j, i});
        }
    }

    int matn = matrix.size();
    /*
    for(int i = 0; i < matn; ++i) {
        while(matrix[i].size() < matn) matrix[i].push_back(matrix[i][matrix[i].size()-1]);
    }*/

    for(int i = 0; i < matn-1; ++i) {
        for(int j = 0; j < order.size(); ++j) {
            int u = matrix[i][j], v = matrix[i+1][j];
            if(layer[u] > layer[v]) std::swap(u, v);
            edges.erase({u, v});
        }
    }

    /*
    if(matn < matrix[0].size()) {
        while(matn < matrix[0].size()) {
            matrix.push_back(matrix[matn-1]);
            ++matn;
        }
    }*/

    for(auto [u, v] : edges) {
        matrix[2*layer[u]+crow][start[u]] = v;
        start[u] += 2;
    }

    return matrix;
}

/*
int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int t;
    std::cin >> t;

    while(t--) {
        int n, m;
        std::cin >> n >> m;

        std::vector<int> a(m), b(m);
        for(int i = 0; i < m; ++i) std::cin >> a[i] >> b[i];
        std::vector<std::vector<int>> matrix = create_map(n, m, a, b);
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[i].size(); ++j) {
                std::cout << matrix[i][j] << " ";
            }
            std::cout << "\n";
        }

        std::cout << "\n";
    }
}*/

///opt/homebrew/bin/g++-14

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