제출 #1254216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254216		TheScrasse	세계 지도 (IOI25_worldmap)	C++20	72 / 100	112 ms	9704 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

#include "worldmap.h"

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    // subtask 5

    vector<vector<ll>> adj(N + 1);
    for (ll i = 0; i < M; i++) {
        adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]);
    }

    vector<vector<vector<ll>>> dp(N + 1);
    vector<ll> pr(N + 1, -1);
    vector<vector<ll>> children(N + 1), subs(N + 1);

    vector<bool> vis(N + 1, false);
    vector<ll> tin(N + 1, -1);
    ll curr_time = 1;

    function<void(ll)> dfs = [&](ll s) {
        vis[s] = true;
        tin[s] = curr_time; curr_time++;
        for (auto u : adj[s]) {
            if (vis[u]) continue;
            pr[u] = s; children[s].pb(u);
            dfs(u);
        }
    };

    dfs(1);

    for (ll i = 0; i < M; i++) {
        ll a = A[i], b = B[i];
        if (tin[a] > tin[b]) swap(a, b);
        if (pr[b] == a) continue;
        subs[a].pb(b);
    }

    auto frame = [&](ll s, vector<ll> v) {
        if (v.empty()) v = {s};
        vector ans(2 * (ll)v.size() - 1, vector<ll>(1, s));
        for (ll i = 0; i < v.size(); i++) ans[2 * i][0] = v[i];
        return ans;
    };

    function<void(ll)> build = [&](ll s) {
        vector<vector<ll>> last = frame(s, subs[s]);
        ll h = last.size() + 2, w = 3;
        for (auto u : children[s]) {
            build(u);
            h = max(h, (ll)dp[u].size() + 2);
            w += dp[u].back().size() + 1;
        }

        dp[s] = vector(h, vector<ll>(w, s));
        ll curr_j = 1;

        auto onion = [&](vector<vector<ll>> v) {
            for (ll i = 0; i < v.size(); i++) {
                for (ll j = 0; j < v.back().size(); j++) {
                    dp[s][i + 1][curr_j + j] = v[i][j];
                }
            }
            curr_j += v.back().size() + 1;
        };

        for (auto u : children[s]) {
            onion(dp[u]);
        }
        onion(last);

        /* cout << "build" _ s << nf;
        for (auto v : dp[s]) {
            for (auto u : v) {
                cout << u << ' ';
            }
            cout << nf;
        } */
    };

    build(1);

    ll sz = max(dp[1].size(), dp[1].back().size());
    vector<vector<int>> ans(sz, vector<int>(sz, 1));

    for (ll i = 0; i < dp[1].size(); i++) {
        for (ll j = 0; j < dp[1].back().size(); j++) {
            ans[i][j] = dp[1][i][j];
        }
    }

    return ans;
}

• 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