Submission #1270335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270335		feining_for_gm	World Map (IOI25_worldmap)	C++20	86 / 100	40 ms	4936 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]+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 < order.size(); ++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; ++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[3*layer[u]-2][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";
    }
}
*/

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