Submission #1254200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254200		TheScrasse	World Map (IOI25_worldmap)	C++20	15 / 100	152 ms	18344 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 2
    ll sz = 240;
    vector<vector<int>> ans(sz, vector<int>(sz, 1));

    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<bool> vis(N + 1, false);
    function<void(ll)> dfs = [&](ll s) {
        vis[s] = true;
        ll h = 2, w = 1;
        for (auto u : adj[s]) {
            if (vis[u]) continue;
            pr[u] = s;
            dfs(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;
        for (auto u : adj[s]) {
            if (pr[s] == u) continue;
            for (ll i = 0; i < dp[u].size(); i++) {
                for (ll j = 0; j < dp[u].back().size(); j++) {
                    dp[s][i + 1][curr_j + j] = dp[u][i][j];
                }
            }
            curr_j += dp[u].back().size() + 1;
        }

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

    dfs(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: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56