제출 #1254225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254225		TheScrasse	World Map (IOI25_worldmap)	C++20	72 / 100	104 ms	8780 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;
    };

    auto transpose = [&](vector<vector<ll>> v) {
        vector w(v.back().size(), vector<ll>(v.size(), 0));
        for (ll i = 0; i < v.size(); i++) {
            for (ll j = 0; j < v.back().size(); j++) {
                w[j][i] = v[i][j];
            }
        }
        return w;
    };

    function<void(ll)> build = [&](ll s) {
        vector<vector<ll>> last = frame(s, subs[s]);
        for (auto u : children[s]) {
            build(u);
        }

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

        auto onion = [&](vector<vector<ll>> v) {
            ll w = dp[s].back().size();
            dp[s].resize(max(dp[s].size(), v.size() + 2));
            for (auto &u : dp[s]) {
                u.resize(w + v.back().size() + 1, s);
            }
            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(transpose(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()) - 1;
    vector<vector<int>> ans(sz, vector<int>(sz, 1));

    for (ll i = 0; i < min(sz, (ll)dp[1].size()); i++) {
        for (ll j = 0; j < min(sz, (ll)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