Submission #1270224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270224		feining_for_gm	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

#include "worldmap.h"
#pragma GCC optimize("O3")
#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;
        if(adj[u].size() == 1 && adj[u][0] == p) {
            tout[u] = order.size()-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]+1;

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

        --mdepth;
    }

    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-1; ++i) {
        for(int j = 0; j < 2*n; ++j) {
            int u = matrix[i][j], v = matrix[i+1][j];
            if(layer[u] > layer[v]) std::swap(u, v);
            edges.erase({u, v});
        }
    }

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

    return matrix;
}

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

    std::vector<std::vector<int>> matrix = create_map(3, 2, {1, 2}, {2, 3});
    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";
    }
}*/

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